P7948 [✗✓OI R1] 前方之风题解

xzyg · 2021-11-17 22:56:42 · 题解

蒟蒻的第一篇题解

题目传送门

Sol 0

暴力模拟+二分

然鹅赛后被 hack 掉了。

Sol 1

排序+后缀和

每次删数必定是从小到大删，考虑对原数组进行排序。对于需判断的一个数 a_p，剩余数只能大于等于 a_p 。

可以维护一个后缀和，O(1) 算出当前 avg-k_i，用一个指针标记当前删数的位置，从而使每次询问优化到 O(n)。

复杂度 O(qn)，期望得分：50pts

Sol 1.5

依照上面的思路，设第 i 个数及后面数的平均数为 avg_i，当前剩余最小数为 a_i。

若 a_i 被 avg_i-k 删掉，如果先不删它，那么它必定也会在下一轮中被 avg_{i+1}-k 删掉。

若 a_i 未被 avg_i-k 删掉，那么即符合要求，停止删数。

可以发现，只需要将 a_i 与 avg_i-k 比较就能确定 a_i 的删除情况。

将这个结论稍加扩展：对于排序后序列中的一个数 a_i，若 a_i 之前的数都被删掉，那么只需要判断 a_i 与 avg_i-k 的大小关系，就可以确定 a_i 的删除情况。

每次询问 O(n) 扫一遍原数组，

复杂度 O(qn)，期望得分：50pts。

~~梅开二度~~

尽管在时间上并没有优化，但在算法简单了许多，只需循环上套个判断就可以了。

Sol 2

考虑对多次查询进行优化。

显然，若 k_i > k_{i+1}，则 avg-k_i < avg-k_{i+1}。限制变大，从而满足条件的数减少、答案减小，可以利用这点进行优化。

其他大佬都是用的双指针，这里介绍另一种~~无脑的~~方法：将询问数组从大到小 sort 一遍，当某个 k 找到答案时，更小的 k 接着往右搜，最后再按编号 sort 回来输出就可以了，这样就可以做到 O(n) 处理。

复杂度：O(n\log n+q\log q) 期望得分：100pts。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct xmh{     //%%%xmh
    ll val,num,ans;
}k[100010];

ll n,q;
ll a[100010];
ll add[100010];
double avg[100010];

inline bool cmp1(xmh a,xmh b){
    return a.val > b.val;
}
inline bool cmp2(xmh a,xmh b){
    return a.num < b.num;
}

void init(){
    memset(a,0,sizeof(a));                      //初始化 
    memset(add,0,sizeof(add));
    memset(avg,0,sizeof(avg));
    memset(k,0,sizeof(k));
    n = 0,q = 0;
    k[0].val = -1,k[0].num = -1,k[0].ans = -1;

   scanf("%lld%lld",&n,&q);
    for(ll i = 1; i <= n; ++i)
        scanf("%lld",&a[i]);
    for(ll i = 1; i <= q; ++i){
        scanf("%lld",&k[i].val);
        k[i].num = i;
    }

    sort(a+1,a+1+n);                            //对原数组及查询数组排序 
    sort(k+1,k+1+q,cmp1);

    add[n] = a[n];
    for(ll i = n-1; i >= 1; --i){               //后缀和 
        add[i] += add[i+1] + a[i];
    }
    for(ll i = 1; i <= n; ++i){                 //平均数 
        avg[i] = 1.0 * add[i] / (n-i+1);
    }
    return;
}

void print(){
    sort(k+1,k+1+q,cmp2);
    for(ll i = 1; i <= q; ++i)
        printf("%lld ",k[i].ans);
    putchar('\n');
}

void process(){
    ll p = 1,sum = n;
    for(ll i = 1; i <= n && p <= q;){
        while(a[i] < avg[i] - k[p].val)++i;     //比较 a[i] 与 avg[i] - k[p] 的关系 
        k[p].ans = n-i+1;                       //满足条件即记录 ans 
        p++;                                    //多次查询优化 
    }
    print();
    return;
}

int main(){
    int T;
    scanf("%d",&T); 
    while(T--){
        init();
        process();
    }
    return 0;
}

upd:

2021.11.28 修改代码里的一些小错误(两个主函数？)

2021.12.17 将 Sol1.5 里的证明修正了一下

2021.12.18 又修了点排版错误淦

P7948 [✗✓OI R1] 前方之风 题解