最近做题小结

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;
		//位置 xx
		for(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);	
		}		

这题就这样了 难！