题解 P6473 【[NOI Online #2 入门组]未了】

· · 题解

贪心+分块

一、算法解析

1.贪心

这个贪心大家都很容易看的出来，由大到小施魔法是最容易达成目的的。证明我就不证了。
但是裸查询的耗时为 O(qn) 。算一下就知道最大是 4×10^{10} 。这个是绝对接受不了的。于是便需要构思优化。

2.优化

这里用了分块来优化查询，将排好序的魔法序列分成大小为 \sqrt{n} 的块，预处理加和。

3.分块大小

如果直接开大小 \sqrt n 的块得出最坏时间复杂度 O(2 \times q \sqrt n) ，算是勉强过关。（在 TLE 的边缘疯狂试探）
所以我们可以思考优化一下，把均摊复杂度降低，我们尝试使每块前大后小（大小等差为1），感性理解一下即可，这样就可以把跳到后面的块所须的多余的时间复杂度均摊到前面的块。然后我们可以得出第一块的大小是为 \frac{\sqrt{8n+1}-1}{2} ，刚好可以覆盖，但是由于是整数，考虑向上取整，且为了避免精度（奇奇怪怪的）问题，取近似值 \sqrt {2n} 即可，时间复杂度为 O(\sqrt2 \times q\sqrt n)。（跑起来比前面一个快了 300ms）

二、代码

#include<bits/stdc++.h>//注意这里的数据范围明显超过了int，所以要开LL
#define LL long long
#define N 1000010
#define s_N 1010
using namespace std;
LL A[N],siz,B[s_N],S[s_N];//B为分块中的和,S为分块边界
int n,L,v;
inline bool cmp(int a,int b){return a>b;}
int solve(LL a)//解决问题
{
    LL sum=L;
    if(sum>a*v) return 0;
    for(int i=1;i<=siz;i++)
    {
        sum+=B[i];//累加一整块
        if(sum>a*v)//答案在刚刚累加的块里
        {
            sum-=B[i];
            for(int j=S[i-1];j<S[i];j++)//在块里逐个累加，知道找到准确答案
            {
                sum+=A[j];
                if(sum>a*v) return j;
            }
        }
    }
    return -1;
}
void get_blank()//分块，并给每个块做累加
{
    int sum=0;
    for(int i=ceil(sqrt(2*n));sum<=n;i--)
    {
        S[siz++]=sum+1;
        sum+=i;
    }
    S[siz]=n+1;
    for(int i=1;i<=siz;i++)
        for(int j=S[i-1];j<S[i];j++)
            B[i]+=A[j];
} 
int main()
{
    cin >> n >> L >> v;
    for(int i=1;i<=n;i++) scanf("%lld",A+i);
    sort(A+1,A+n+1,cmp);
    get_blank();
    int q;
    cin >> q;
    while(q--)
    {
        LL a;
        scanf("%lld",&a);
        cout << solve(a) << '\n';
    }
    return 0;
}