ABC373E 题解

题目大意

$n$ 个候选人目前各有一些选票 $a_i$，总共选民投出了 $k$ 张选票。现在有 $k-\sum a_i$ 张可支配选票。现在请你求出第 $i$ 个人至少需要多少票使得剩下的票无论投给谁他都可以当选。

当选规则是：当且仅当选票比他多的人 $<m$。

如果无法当选即为 $-1$

Solution

鲜花：

可爱题。

这个题目很好想啊，即使是在 D 题被卡、同舍生皆开 E 的情况下，没花几分钟就想到了怎么做了。一度怀疑读错题了。

就是一个萌萌二分算代价是否合法。

但是调的时候是很麻烦的，总有一些边界问题。考后几分钟就 A 了。

解法：

首先从大到小排序，得到初始选票支持情况。

接着对于每个 $i$ 都二分他的增量 $mid$。

我们把选票统计抽象成条形统计图，一开始是非严格递减的。现在 $i$ 这个位置突然多了 $mid$ 的增量，就把他挪到合适的位置使得这个图再次非严格递减。设这个位置为 $p$。

我们考虑如何 ban 掉他。无非就是他后面 $m-p+1$ 个位置的值得到了选票都比他高了，那么使得这一情况发生需要多少选票呢？

显然为：

$$ (a_i+mid+1)\times(m-p+1)-\sum\limits_{j=p}^m a_j $$

这个 $\sum$ 在排序前维护一下前缀和就行了。

只有上式加上让 $i$ 激增的增量 $mid$ 后的值小于等于剩余选票数，才有可能 ban 掉他。

现在在考虑一种情况：如果本来 $i$ 初始就在 $1\sim m$ 内呢？

会发现如果我们用上式计算，会把他自己也算进“ban 掉他”的大军里。所以要往后多算一个，再把他自己给加上。

$$ (a_i+mid+1)\times(m-p+1)-\sum\limits_{j=p}^{m+1} a_j+a_i $$

然后就可以实现了，注意小于大于这种情况要不要等于。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90


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

#define int long long
#define pii pair<int,int>
#define ft first
#define sd second

const int N=2e5+5;

int n,m,k;
pii a[N];
int ans[N],sum[N];
int b[N];

int work(int x)
{
    int l=1,r=n,res=1;
    while(l<=r){
        int mid=l+r>>1;
        if(b[mid]<=x)
            res=mid,r=mid-1;
        else
            l=mid+1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    int tot=0;
    for(int i=1;i<=n;i++)
        cin>>a[i].ft,a[i].sd=i,tot+=a[i].ft;
    int Dt=k-tot;
    if(n==m){
        for(int i=1;i<=n;i++){
            cout<<"0 ";
        }
        exit(0);
    }
    sort(a+1,a+n+1,[](pii x,pii y){
        if(x.ft!=y.ft)
            return x.ft>y.ft;
        return x.sd<y.sd;
    });
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i].ft,b[i]=a[i].ft;

    for(int i=1;i<=n;i++){
        int l=0,r=Dt,res=-1;
        if(a[i].ft+Dt<a[m].ft){
            ans[a[i].sd]=-1;
            continue;
        }
        while(l<=r){
            int mid=l+r>>1;
            if(i<=m){
                int p=work(a[i].ft+mid);
                if(p>m){
                    l=mid+1;
                    continue;
                }
                if((a[i].ft+mid+1)*(m-p+1)-(sum[m+1]-a[i].ft-sum[p-1])+mid>Dt){
                    res=mid;
                    r=mid-1;
                }else
                    l=mid+1;
            }else{
                int p=work(a[i].ft+mid);
                if(p>m){
                    l=mid+1;
                    continue;
                }
                if((a[i].ft+mid+1)*(m-p+1)-(sum[m]-sum[p-1])+mid>Dt){
                    res=mid;
                    r=mid-1;
                }else
                    l=mid+1;
            }
        }
        ans[a[i].sd]=res;
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}