Codeforces 639E - Bear and Paradox（二分+贪心）

原来 jxd 作业里也有我会做的题 i 了 i 了

首先这种题目的套路就是先考虑对于一个固定的 \(c\)，怎样求出得分最高的策略，而类似于这样的问题都考虑贪心求解，手玩几组数据就能发现最优方案是将所有题目按照 \(\dfrac{p_i}{t_i}\) 从大到小排列。简单证明一下，考虑按照 P4437 排列的套路，假设有两道题 \(i,j\) 满足 \(\dfrac{p_i}{t_i}>\dfrac{p_j}{t_j}\)，那么将 \(i\) 放在 \(j\) 前面的得分为 \(W_1=p_i(1-\dfrac{ct_i}{T})+p_j(1-\dfrac{c(t_i+t_j)}{T})\)，将 \(i\) 放在 \(j\) 后面的得分为 \(W_2=p_j(1-\dfrac{ct_j}{T})+p_i(1-\dfrac{c(t_i+t_j)}{T})\)，做差可得 \(\Delta=W_1-W_2=\dfrac{c(p_it_j-p_jt_i)}{T}\)，而由 \(\dfrac{p_i}{t_i}>\dfrac{p_j}{t_j}\) 知 \(p_it_j-p_jt_i>0\)，故 \(\Delta>0\)，也就是说将 \(i\) 放在 \(j\) 前面最优，至于 \(\dfrac{p_i}{t_i}\) 相同的 \(i\)，一定有 \(\Delta=0\)，也就是说 \(\dfrac{p_i}{t_i}\) 相同的 \(i\) 可以随意交换位置。据说这套路还有个专门名字叫什么 Exchange arguments？不过名字啥的不重要辣，MO 里一般叫它调整法，反正这东西在 OI 和 MO 里都挺有用的就对了（

接下来考虑怎样求答案。首先这个 \(c\) 满足单调性，故考虑二分答案，这是题目中疯狂暗示的，再想不到就有些 sb 了罢（别打我）。考虑检验某个 \(c\) 是否合法，我们显然可以确定每道题可能被完成的最靠前的时间，以及每道题可能被完成的最靠后的时间。具体来说，我们将 \((p_i,t_i)\) 按从大到小顺序排序，记 \(sum_i\) 为对于排好序的 \(t_i\)，\(\sum\limits_{j=1}^it_j\) 的值。考虑对于一段极长的区间 \([l,r]\) 满足 \(\forall x,y\in [l,r]\) 都有 \(\dfrac{p_x}{t_x}=\dfrac{p_y}{t_y}\)，那么显然对于 \(i\in [l,r]\)，问题 \(i\) 可能被完成的最靠前的时间为 \(sum_{l-1}+t_i\)，最靠后的时间为 \(sum_r\)。因此我们只需检验是否 \(\exist i,j\) 满足 \(p_i>p_j\)，完成 \(i\) 最少可能的得分 \(<\) 完成 \(j\) 最大可能的得分，这个可以通过再将所有题目按 \(p_i\) 排序并用 two pointers 维护 \(mx=\max\limits_{p_j<p_i}p_j(1-\dfrac{c·mxt_j}{T})\)，其中 \(mxt_j\) 即为上文中所说的问题 \(i\) 可能的最靠后的完成时间。并与 \(i\) 在可能的最靠前的完成时间的得分比较即可。

时间复杂度 \(\mathcal O(n\log n)\)。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=1.5e5;

const double EPS=1e-9;

int n;ll T,sum[MAXN+5];

struct data{ll p,t,mn,mx;} a[MAXN+5];

bool cmp1(data lhs,data rhs){return lhs.p*rhs.t>rhs.p*lhs.t;}

bool cmp2(data lhs,data rhs){return lhs.p<rhs.p;}

bool check(double x){

	double mx=0;

	for(int i=1,j=1;i<=n;i++){

		while(a[j].p!=a[i].p) chkmax(mx,1.0*a[j].p*(1-x*a[j].mn/T)),j++;

		if(1.0*a[i].p*(1-x*a[i].mx/T)<mx) return 0;

	} return 1;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i].p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i].t),T+=a[i].t;

	sort(a+1,a+n+1,cmp1);

	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].t;

	for(int l=1,r;l<=n;l=r+1){

		r=l;while(r<n&&a[r].p*a[r+1].t==a[r].t*a[r+1].p) r++;

		for(int i=l;i<=r;i++) a[i].mx=sum[r],a[i].mn=sum[l-1]+a[i].t;

	} sort(a+1,a+n+1,cmp2);

	double l=0,r=1.0,x=-114514.1919810;

	while(fabs(r-l)>EPS){

		double mid=(l+r)/2.0;

		if(check(mid)) x=l=mid;

		else r=mid;

	} printf("%.10lf\n",x);

	return 0;

}

巴特西

Codeforces 639E - Bear and Paradox（二分+贪心）

最新文章

热门文章