poj 3266 (01分数规划+平衡树维护凸壳)

题意: 

 

Bessie考了N科(N≤50000),每科的得分为Ti,满分为Pi(样例似乎是五科红灯……)。

现在Bessie的老师要给她们统计最终得分,方法 是先算出每一科得分的百分比,去除D个百分比最低的科目,然后剩下科目的∑T / ∑P就是最终得分的百分比。

很幸运,没有人有两科的得分比一样。Bessie的数学很牛X,她马上就发现她的老师在坑爹,因为有时候可以通过去除不同的科 目来获得更高的分数。

现在Bessie想知道,对于哪些D值,她可以通过去除与老师不同的D科,从而获得更高的分数呢?

(摘自http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html)

 

做法:

 

假设现在取了i个百分比靠前的科目,当前的综合百分比是k。

 

如果能把选的科目p替换成一个没选的科目q使得综合百分比提高 ,根据01分数规划的思想,显然 p.T-k*p.P<q.T-k*q.P 。

 

于是就可以在选的科目中找一个科目 p 使得 p.T-k*p.P最小,再在没选的科目中找一个科目 q 使 q.T-k*q.P 最大 。

 

然后发现 T-k*P 就是向量的点积 (1,-k)*(T,P) ,就可以用平衡树维护两个凸壳来找最大值和最小值。

 

注意到:排序后 选的科目越多,综合百分比越低,因此k是单调的,于是便不需要在平衡树里二分查找了。

 

网上题解说可以用单调栈,但是总感觉有问题,还是用了平衡树。

 

我依旧是把上凸壳转化成下凸壳用同一个函数来做。

#include<cstdio>
#include<map>
#include<algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef map<int,int>::iterator itr;
const int N=50005;
int n;
double k[N],fmax[N],fmin[N];
int ans[N];
struct P
{
	int x,y;
	P operator-(const P &t)const
	{
		return {x-t.x,y-t.y};
	}
	int operator^(P t)
	{
		return x*t.y-y*t.x;
	}
}a[N];
bool cmp(P a,P b)
{
	return 1.0*a.y/a.x>1.0*b.y/b.x;
}
double dot(itr it,double x,double y)
{
	return it->X*x+it->Y*y;
}
ll cross(itr l,P p2,itr r)
{
	P p1={l->X,l->Y},p3={r->X,r->Y};
	return (p2-p1)^(p3-p2);
}
struct hull
{
	map<int,int>s;
	itr mid,l,r,p1,p2;
	void init() { s.clear(); }
	itr pre(itr it)
	{
		if (it==s.end()) return it;
		if (it==s.begin()) return s.end();
		return --it;
	}
	itr suc(itr it)
	{
		if (it==s.end()) return it;
		return ++it;
	}
	bool inside(P p)
	{
		if (s.empty()) return 0;
		r=s.lower_bound(p.x);
		if (r==s.end()) return 0;
		if (r->X==p.x) return p.y>=r->Y;
		if (r==s.begin()) return 0;
		l=r; l--;
		return cross(l,p,r)<=0;
	}
	void add(P p)
	{
		if (inside(p)) return;
		s[p.x]=p.y;
		mid=s.find(p.x);
		p1=suc(mid); p2=suc(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)<=0)
			s.erase(p1),p1=p2,p2=suc(p2);
		p1=pre(mid); p2=pre(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)>=0)
			s.erase(p1),p1=p2,p2=pre(p2);
	}
	double get(double x,double y)
	{
		r=s.end(); r--;
		l=pre(r);
		while(l!=s.end()&&dot(l,x,y)<=dot(r,x,y))
			s.erase(r),r=l,l=pre(l);
		return dot(r,x,y);
	}
}G;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x);
	sort(a+1,a+n+1,cmp);
	double sumT=0,sumP=0;
	for (int i=1;i<=n;i++) sumT+=a[i].y,sumP+=a[i].x,k[i]=sumT/sumP;
	G.init();
	for (int i=1;i<=n;i++)
	{
		G.add(a[i]);
		fmin[i]=G.get(-k[i],1);
	}
	G.init();
	for (int i=n;i>=2;i--)
	{
		G.add({a[i].x,-a[i].y});
		fmax[i-1]=-G.get(k[i-1],1);
	}
	int cnt=0;
	for (int i=1;i<n;i++)
		if (fmin[i]<fmax[i]) ans[++cnt]=n-i;
	printf("%d\n",cnt);
	for (int i=cnt;i>=1;i--) printf("%d\n",ans[i]);
}