ABC-373-E - How to Win the Election · znzryb
## 题目大意
有 N 个候选人争夺 M 个席位，共有 K 张票。目前已知每个候选人已获得的票数，以及剩余未投的票数。对于每个候选人，判断在最坏情况下（即剩余票数的分配对他最不利时），他是否还能通过获得一定数量的剩余票数来确保当选（进入前 M 名）。如果是，求出他至少需要再获得多少票；否则输出 -1。
## AC代码
二分答案，检查器的设计重点在于
`// 防止选用自己作为自己的竞争对手`
```cpp
if(idx-needOver-rectifyIdx<0) // <0 说明人不够了，一共就没那么多人（n=m）
return true;
```
[https://atcoder.jp/contests/abc373/submissions/58823933](https://atcoder.jp/contests/abc373/submissions/58823933)
二分检查器的核心行（加粗行）思路
```cpp
#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`**`))`**`;的来历`**
半成品代码
```cpp
#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](https://atcoder.jp/contests/abc373/submissions/58808859)
五彩缤纷的提交
我做着做着发现完全不需要分两种情况，这个提交是分两种情况的。
然后check（）可以用前缀和优化
[](https://www.notion.so/11e4539447bd8050b6efe65de47ef675) 像这道题一样
```cpp
#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;
}
```