pj难度的一场模拟赛,得分300/400.


完美夏冰

签到题。

#include<bits/stdc++.h>
using namespace std;
int a[4];
int main()
{
    cin>>a[0]>>a[1]>>a[2]>>a[3];
    sort(a,a+4);
    puts(a[0]+a[3]==a[1]+a[2]?"Perfect":"Biu");
    return 0;
}

疯狂秋风

看到k的范围这么小,就要把时间复杂度往k上靠。

把数据从小到大排序之后观察到,两个数排名都大于k的二元组(如a[k+1]+a[k+2])是不可能排到第k小的。于是双重循环只需要跑到k即可。时间复杂度$O(k^2)$。

#include<bits/stdc++.h>
using namespace std;
int a[100010];
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=min(k,n);i++)
        for(int j=1;j<=min(k,n);j++)
            q.push(a[i]+a[j]);
    for(int i=1;i<k;i++)
        q.pop();
    printf("%d\n",q.top());
    return 0;
}

极端寒冬

暂未想到合适解法。


风吹樱花

大致题意:

给定长度为$n$的序列$A$与一个数$k$,要求构造一个$x$序列满足$x_1+x_2+..x_n=k$并且$a_1*(x_1)^2+a_2*(x_2)^2...a_n*(x_n)^2$最小,输出这个最小值。

首先想到把序列A从小到大排序,那么对应的x应该是不上升的。

那么最简单的一个不上升的序列就是把k全部叠到$x_1$上。初始的ans的值就是$a_1*k^2$

然后可知$a^2-(a-1)^2=2a-1,(a+1)^2-a^2=2a+1$。

所以我们要把$x_1$上的一部分k分到其他a身上。如果从$x_1$身上分1给$x_i$,那么第一项减少的权值就是$a_1*(2*x_1-1)$,第$i$项增加的权值就是$a_i*(2*x_i+1)$,如果减少的比增加的多,那明显应该操作,即ans-=(a_1*(2*x_1-1)-a_i*(2*x_i+1))

不仅如此,还要贪心地选择增加的权值最小的那个$a_i*(2*x_i+1)$,这样能让操作最优化。

于是大致思路就是每次找到一个最小的$a_i*(2*x_i+1)$,如果它小于第一项减少的权值,那么就进行操作并继续下去,否则说明继续操作不能更优了,返回。

这一步操作用优先队列优化降到log级别即可通过。

总时间复杂度$O(klogn)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x[100010];
int a[100010];
struct node
{
    int val,id;
    bool operator < (const node &a) const
    {
        return a.val<val;
    }
};

priority_queue<node> q; 
signed main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    int ans=a[1]*k*k,flag=1;
    if(n==1)
    {
        printf("%lld\n",ans);
        return 0;
    }
    x[1]=k;
    for(int i=2;i<=n;i++)
        q.push((node){a[i]*(2*x[i]+1),i});
    int fst=a[1]*(2*x[1]-1);
    while(fst>q.top().val)
    {
        node tmp=q.top();
        q.pop();
        ans-=(fst-tmp.val);
        x[tmp.id]++;
        q.push((node){a[tmp.id]*(2*x[tmp.id]+1),tmp.id});
        x[1]--;
        fst=a[1]*(2*x[1]-1);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 09 月 12 日 08 : 39 PM