Znzryb's Blog
0%

ABC-373-E - How to Win the Election

Posted on Edited on

题目大意

有 N 个候选人争夺 M 个席位，共有 K 张票。目前已知每个候选人已获得的票数，以及剩余未投的票数。对于每个候选人，判断在最坏情况下（即剩余票数的分配对他最不利时），他是否还能通过获得一定数量的剩余票数来确保当选（进入前 M 名）。如果是，求出他至少需要再获得多少票；否则输出 -1。

AC代码

二分答案，检查器的设计重点在于
// 防止选用自己作为自己的竞争对手

1
2
if(idx-needOver-rectifyIdx<0)  // <0 说明人不够了，一共就没那么多人（n=m）
        return true;

https://atcoder.jp/contests/abc373/submissions/58823933

二分检查器的核心行（加粗行）思路

image

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll diff=0;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi,rectify=0,rectifyIdx=0;
    // 防止选用自己作为自己的竞争对手
    ll candidateIdx=li[indexOfCandidate]-1;
    if(candidateIdx<=idx && candidateIdx>idx-needOver) {
        rectify=oa[indexOfCandidate],rectifyIdx=1;
    }
    // hand 11 过不了原因是n=m，我没有考虑人不够的情况 不知道他给你指到哪里去了
    if(idx-needOver-rectifyIdx<0)  // <0 说明人不够了，一共就没那么多人（n=m）
        return true;
    diff=gainBallots+(currBallots+1)*needOver-(sumA[idx]-sumA[idx-needOver-rectifyIdx]-rectify);
    // 就是下面循环的前缀和写法
    // for(ll i=idx;cnt<needOver;i--) {
    //     diff+=(currBallots+1-a[i]);
    //     cnt++;
    // }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=0,r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
        oa[i]=a[i];
    }
    remain=k-countedBallots;
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {     // 前缀和
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        ans[i]=bsearch(i);
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
// 只WA了一个点 https://atcoder.jp/contests/abc373/submissions/58815831
// AC https://www.luogu.com.cn/record/182236761
// AC https://atcoder.jp/contests/abc373/submissions/58823933

心路历程

我现在的想法就是我认为这就是博弈论，就是我投的票要竭力使这个人掉出m人的队列，而然后剩余的票一定是投在这个人身上
ans[i]=ceil((remain-diff)*1.0/(cnt+1));的来历

image

半成品代码

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
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],toli[N]; // toli是通过a下标访问li的转介层
ll borderlineStand=0; // 临界标准，说人话就是不满足条件但最大的。
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
void debug() {
    cout<<"stand: "<<stand<<" borderlineStand:"<<borderlineStand<<endl;
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<li[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<toli[i]<<" ";
    }
    cout<<endl<<"ans: ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
        else
            borderlineStand=max(borderlineStand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
        for(ll j=s;j<e;j++) {
            toli[j]=i;       // toli 也可以认为是排序后元素位置->排序前元素位置
        }
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi+1-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }
    }
    debug();
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}

https://atcoder.jp/contests/abc373/submissions/58808859

五彩缤纷的提交

我做着做着发现完全不需要分两种情况，这个提交是分两种情况的。

然后check（）可以用前缀和优化

像这道题一样

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
91
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi;
    ll cnt=0,diff=gainBallots;
    for(ll i=idx;cnt<needOver;i--) {
        diff+=(currBallots+1-a[i]);
        cnt++;
    }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=stand-oa[i],r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }else {         // 这里是原来没选上，如何在剩余选票中抢到位置
            ans[i]=bsearch(i);
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}