专栏首页饶文津的专栏【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)

【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)

题意

小牛参加了n个测试,第i个测试满分是??pi,它的得分是??ti。老师去掉??/??ti/pi最小的d个测试,将剩下的总得分/总满分作为小牛的得分。小牛想知道多少个d存在比老师计算的分数更高的选择测试的方案,并输出这些d。

题解

基础思路

法1 平衡树维护动态凸包

法2 普通维护凸包

法3 分治dp

由于决策单调,计算?[?],?[?]f[j],g[j]时还可以分治计算。

代码

//平衡树动态维护凸包
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,l,r) for(int i=l,_=r;i<_;++i)
#define per(i,l,r) for(int i=r-1,_=l;i>=_;--i)
typedef long long ll;
typedef double dd;
const int INF=0x3f3f3f3f;
const int N=50100;

struct nd{
	ll t,p;
	bool operator < (const nd&b)const{
		return t*b.p<p*b.t;
	}
}a[N];

struct DynmcCnvx{
	int rot,fa[N],c[N][2];
	dd lk[N],rk[N],x[N],y[N];
	void zigzag(int x,int &rot){
		int y=fa[x],z=fa[y];
		int p=(c[y][1]==x),q=p^1;
		if (y==rot) rot=x;
		else if (c[z][0]==y) c[z][0]=x; 
		else c[z][1]=x;
		fa[x]=z; fa[y]=x; fa[c[x][q]]=y;
		c[y][p]=c[x][q]; c[x][q]=y; 
	}
	void splay(int x,int &rot){
		while (x!=rot){
			int y=fa[x],z=fa[y];
			if (y!=rot) zigzag(((c[y][0]==x)^(c[z][0]==y))?x:y,rot);
			zigzag(x,rot);
		}
	}
	void insert(int &t,int anc,int now){//加入平衡树
		if (!t) t=now, fa[t]=anc;
		else insert(c[t][x[now]>x[t]],t,now);
	}
	void update(int t){//加入点(x[t],y[t]),维护上凸壳。
		splay(t,rot);
		if (c[t][0]){//向左求凸包
			int left=prev(rot);
			splay(left,c[rot][0]); c[left][1]=0;
			lk[t]=rk[left]=getk(left,t);
		}
		else lk[t]=INF;
		if (c[t][1]){//向右求凸包
			int right=succ(rot);
			splay(right,c[rot][1]); c[right][0]=0;
			rk[t]=lk[right]=getk(t,right);
		}
		else rk[t]=-INF;
		if (lk[t]<=rk[t]){//在原凸包内部的情况,直接删掉该点 
			rot=c[t][0]; c[rot][1]=c[t][1]; fa[c[t][1]]=rot; fa[rot]=0;
			lk[rot]=rk[c[t][1]]=getk(rot,c[t][1]);
		}
	}
	dd getk(int i,int j){//求斜率
		if (x[i]==x[j]) return -INF;
		return (y[j]-y[i])/(x[j]-x[i]);
	}
	int prev(int rot){//求可以和当前点组成凸包的右边第一个点
		int t=c[rot][0],tmp=t;
		while (t){
			if (getk(t,rot)<=lk[t]) tmp=t,t=c[t][1];
			else t=c[t][0];
		}
		return tmp;
	}
	int succ(int rot){//求可以和当前点组成凸包的左边第一个点
		int t=c[rot][1],tmp=t;
		while (t){
			if (getk(rot,t)>=rk[t]) tmp=t,t=c[t][0];
			else t=c[t][1];
		}
		return tmp;
	}
	int find(int t,dd k){//找到当前斜率的位置,即找到最优值
		if (!t) return 0;
		if (lk[t]>=k && k>=rk[t]) return t;
		return find(c[t][lk[t]>=k],k);
	}
  
	void Init(){
		rot=0;mem(fa,0);mem(c,0);
	}
	dd GetMax(dd a,dd b){//max{ax+by}
		int j=find(rot,-a/b);
		return a*x[j]+b*y[j];
	}
	void InsertPoint(int i,dd _x,dd _y){//插入点(x,y)
		x[i]=_x,y[i]=_y;
		insert(rot,0,i);
		update(i);
	}
}s;

dd st,sp;
dd f[N],g[N];
int ans[N],cnt;
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rep(i,1,n+1)
		cin>>a[i].t>>a[i].p;
	sort(a+1,a+n+1);
	per(i,1,n+1){
		s.InsertPoint(i,-a[i].p,-a[i].t);
		f[i-1]=-s.GetMax(-(st+=a[i].t),sp+=a[i].p);
	}
	s.Init();
	rep(i,1,n){
		s.InsertPoint(i,a[i].p,a[i].t);
		g[i]=s.GetMax(-(st-=a[i].t),sp-=a[i].p);
		if(g[i]>f[i]) ans[cnt++]=i;
	}
	cout<<cnt<<endl;
	rep(i,0,cnt)cout<<ans[i]<<endl;
	return 0;
}
//直接维护凸包
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_=r;i<_;++i)
#define per(i,l,r) for(int i=r-1,_=l;i>=_;--i)
typedef long long ll;
const int N=50100;

struct nd{
	ll t,p;
	bool operator < (const nd&b)const{
		return t*b.p<p*b.t;
	}
}a[N];

struct Po{
	ll x,y;
	Po(ll x=0,ll y=0):x(x),y(y){}
	Po operator -(const Po&b)const {return Po(x-b.x,y-b.y);}
	Po operator +(const Po&b)const {return Po(x+b.x,y+b.y);}
	ll operator ^(const Po&b)const {return x*b.y-y*b.x;}
	ll operator *(const Po&b)const {return x*b.x+y*b.y;}
}p[N];
ll xmul(const Po&a,const Po&b,const Po&o){
	return (a-o)^(b-o);
}

struct DownCnvx{
	Po q[N];int top;
	//顺时针方向维护下凸壳
	void Insert(Po p){
		while(top && q[top].x<=p.x) --top;
		while(top>1 && xmul(q[top],p,q[top-1])>=0)--top;
		q[++top]=p;
	}
	ll GetMin(Po p){
		while(top>1 && p*q[top]>=p*q[top-1])--top;
		return q[top]*p;
	}
}d;

struct UpCnvx{
	Po q[N];int top;
	//顺时针方向维护上凸壳
	void Insert(Po p){
		while(top && q[top].x>=p.x) --top;
		while(top>1 && xmul(q[top],p,q[top-1])>=0)--top;
		q[++top]=p;
	}
	ll GetMax(Po p){
		while(top>1 && p*q[top]<=p*q[top-1])--top;
		return q[top]*p;
	}
}u;

ll st,sp;
ll f[N],g[N];
int cnt,ans[N];
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rep(i,1,n+1)
		cin>>a[i].t>>a[i].p;
	sort(a+1,a+n+1);
	per(i,1,n+1){
		d.Insert(Po(a[i].p,a[i].t));
		f[i-1]=d.GetMin(Po(-(st+=a[i].t),sp+=a[i].p));
	}
	rep(i,1,n+1){
		u.Insert(Po(a[i].p,a[i].t));
		g[i]=u.GetMax(Po(-(st-=a[i].t),sp-=a[i].p));
		if(g[i]>f[i]) ans[cnt++]=i;
	}
	cout<<cnt<<endl;
	rep(i,0,cnt)cout<<ans[i]<<endl;
	return 0;
}
//分治优化
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l,_=r;i<_;++i)
#define per(i,l,r) for(int i=r-1,_=l;i>=_;--i)
typedef long long ll;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=50100;

struct nd{
	ll t,p;
	bool operator < (const nd&b)const{
		return t*b.p<p*b.t;
	}
}a[N];

ll st[N],sp[N];
ll f[N],g[N];
int cnt,ans[N];
int n;
void solveMax(int l,int r,int optL,int optR){
	if(l>r)return;
	int j=l+r>>1,u=optL;
	rep(i,optL,min(optR,j)+1){
		ll tmp=sp[j]*a[i].t-st[j]*a[i].p;
		if(tmp>g[j])g[j]=tmp,u=i;
	}
	solveMax(l, j-1, optL, u);
	solveMax(j+1, r, u, optR);
}
void solveMin(int l,int r,int optL,int optR){
	if(l>r)return;
	int j=l+r>>1,u=optL;
	rep(i,max(optL,j+1),optR+1){
		ll tmp=sp[j]*a[i].t-st[j]*a[i].p;
		if(tmp<f[j])f[j]=tmp,u=i;
	}
	solveMin(l, j-1, optL, u);
	solveMin(j+1, r, u, optR);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rep(i,1,n+1)
		cin>>a[i].t>>a[i].p;
	sort(a+1,a+n+1);
	per(i,1,n+1){
		st[i-1]=st[i]+a[i].t;sp[i-1]=sp[i]+a[i].p;
		f[i]=LINF;g[i]=-LINF;
	}
	solveMax(1,n,1,n);
	solveMin(1,n,1,n);
	rep(i,1,n)
		if(f[i]<g[i])ans[cnt++]=i;
	cout<<cnt<<endl;
	rep(i,0,cnt)cout<<ans[i]<<endl;
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU 5438】Ponds

    存边的时候,要头尾都存这个边。用dfs或者队列删点,再用并查集或者dfs确定联通块,然后统计联通块的点数,最后累加。

    饶文津
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 【POJ 3321】Apple Tree

    有n个节点以1为根节点的树,给你树的边关系u-v,一开始每个节点都有一个苹果,接下来有两种操作,C x改变节点x的苹果状态,Q x查询x为根的树的所有苹果个数。

    饶文津
  • C语言——小学题目B卷解析(终)

    第6题,简单说明:系统有默认的转化规则,就是从精度底的转化为精度高的,避免计算时精度的丢失。coding一下:

    Ed_Frey
  • 挑战程序竞赛系列(8):2.1一往直前!贪心法(其他)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 洛谷P2831 愤怒的小鸟(状压dp)

    直接状压dp一下,\(f[sta]\)表示干掉\(sta\)这个集合里面的鸟的最小操作数

    attack
  • BZOJ3498: PA2009 Cakes(三元环)

    如果\(v\)的度数\(\leqslant M\),那么就再暴力枚举\(v\)连出去的点\(t\),看\(u\)与\(t\)是否联通(打标记)

    attack
  • 1087 有多少不同的值 (20 分)

    当自然数 n 依次取 1、2、3、……、N 时,算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值?(注:⌊x⌋ 为取整函数,表示不超过 x 的最大自然...

    可爱见见
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • 使用高级程序设计语言实现集合的交并差运算

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券