https://www.luogu.com.cn/problem/AT_abc373_e
这道题是个二分 然后标答是两个二分 我用的树组+二分
需要对代数式进行拆分才能得到
我一开始看错题目了 看成大于等于他的票的人不多于M就行
然后就很简单 我觉得可以改编下这个题
很明显 最终前m个人一定当选
那么对于每一个人 我们就是尽量求他能不能利用最后的票让自己当选
求这个票的最小值
那我们先进行排序 从小到大排好
对于已经排前M的人来说 我们把他给抹掉 然后让m+1的人变成m位
此时我们对他进行二分判断最小 因为虽然我已经排前m了 但是
票数多太多的情况下 还是会被反超
对于这个抹掉可以写一个change函数 然后 后面再加上去就行
难就难在这个树状树组的写法上
现在分情况讨论 如果我已经前m位了 现在我删掉自己
二分了一个 ans可以进前m位的第2假设m为5 此时 假设多的票数总共是sum
sum-ans要让3 4 5 不可以反超 则有后面的总和加上sum-ans小于等于3*（ans+ai）这样就可以做到了
说白了就是后面的所有票数要小于人数*（ai+ans+1）
不能等于
这种求和用树组是log操作 明显可以做 对于查找位置 可以
内置lowerbound upperbound进行查找
为了查多少名不是通过low upp 因为他们返回的是数值
所以必须开再一开一个树组进行访问
struct Tree{int tr[range];void modify(int x,int d){int dex=lower_bound(num+1,num+1+cnt,x)-num;//位置 xxfor(int i=dex;i<=cnt;i+=i&-i){tr[i]+=d;}
// for(int i=dex;i<=cnt;i+=i&-i)
// {
// cout<<tr[i]<<" "<<i<<" "<<x<<" "<<dex<<endl;
// }}int query(int x){int res=0;int dex=upper_bound(num+1,num+1+cnt,x)-num-1;
// cout<<dex;
// for(int i=dex;i>=0;i-=i&-i)for(int i=dex;i;i-=i&-i){res+=tr[i];}
// cout<<"res:"<<res<<endl;return res;}
}t1,t2;
挺不容易的
考虑建树 只需要 枚举前m位
k=k-sum;sort(num+1,num+1+cnt);cnt=unique(num+1,num+1+cnt)-num-1;sort(a+1,a+1+n,cmp);
//离散 for(int i=1;i<=m;i++){t1.modify(a[i].x,a[i].x);t2.modify(a[i].x,1);}
后面删除：
if(i<=m){t1.modify(a[i].x,-a[i].x);t2.modify(a[i].x,-1);t1.modify(a[m+1].x,a[m+1].x);t2.modify(a[m+1].x,1); }
这题就这样了 难！
