BZOJ 3874 [Ahoi2014]宅男计划 【三分+贪心】

tonyfang posted @ 2016年3月06日 08:43 in BZOJ with tags c++ oi , 762 阅读

【题解】三分次数,然后贪心求解。

但是这个函数不一定是凸函数,有可能是平的,所以三分的时取得点离得要远一点。

或者 二分后套三分也可以。

 

# include <stdio.h>
# include <algorithm>
using namespace std;

long long m,f;
int n;

const int M=210;
struct food {
	long long p,s;
}a[M],b[M];
long long ans=0;

inline bool cmp(food a,food b) {
	if(a.s!=b.s) return a.s<b.s;
	else return a.p<b.p;
}

inline long long g(long long t) {
	long long ret=0,s=m-t*f;
	if(s<0) return 0;
	long long d=0;
	for (int i=1;i<=n;++i) {
		if(a[i].s+1<=d) continue;
		long long tt=min(a[i].s+1-d,s/t/a[i].p);
		ret=ret+t*tt; d+=tt;
		s-=t*tt*a[i].p;
		if(a[i].s+1<=d) continue;
		long long ttt=min(t,s/a[i].p);
		if(ttt>0) {
			ret+=ttt;
			break;
		}
	}
	return ret;
}

int main() {
	scanf("%lld%lld%d",&m,&f,&n);
	for (int i=1;i<=n;++i) 
		scanf("%lld%lld",&a[i].p,&a[i].s);
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;++i) {
		b[i].p=a[i].p;
		b[i].s=a[i].s;
	}
	int pos=1;
	for (int i=2;i<=n;++i) {
		if(a[pos].s==b[i].s && a[pos].p<b[i].p) continue;
		while(pos>0 && a[pos].s<b[i].s && a[pos].p>=b[i].p) --pos;
		a[++pos]=b[i];
	}
	n=pos;
	
	long long l=1,r=m/(f+a[1].p);
	while(l<=r) {
		long long mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		long long le=g(mid1),ri=g(mid2);
		ans=max(ans,le);
		ans=max(ans,ri);
		if(le<ri) l=mid1+1;
		else r=mid2-1;
	}
	printf("%lld\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter