• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【CF639E】Bear and Paradox(贪心+二分)

开发技术 开发技术 1周前 (05-04) 9次浏览

点此看题面

  • (n)个问题,第(i)个问题初始分为(p_i),耗时(t_i),并设(T=sum_{i=1}^nt_i)
  • 你可以按某种顺序依次完成所有问题,若在时刻(x)完成了第(i)个问题,则该问题的最终分为(p_icdot(1-frac {cx}T))
  • 求最大的(cin[0,1]),满足在任意一个能使最终分总和最大的做题顺序中,都不存在某两个问题(i,j),使得(i)的初始分比(j)小,(i)的最终分比(j)大。
  • (nle1.5times10^5)

最优做题顺序(贪心)

我们要最大化(sum_{i=1}^np_icdot(1-frac{cx_i}T)=sum_{i=1}^np_i-frac cTcdotsum_{i=1}^np_ix_i),也就是要最小化(sum_{i=1}^np_ix_i),而这是一个与(c)无关的式子。

然后对于连续完成的两个问题(i,j),考虑它们谁放在前面更优,那么(i)优于(j)就需要满足:(假设先前花费总时间为(s)

[p_itimes(s+t_i)+p_jtimes(s+t_i+t_j)<p_jtimes(s+t_j)+p_itimes(s+t_i+t_j)
]

化简一下得到一个很简单的式子:

[p_jtimes t_i<p_itimes t_j
]

所以我们可以预先把所有问题按照(frac{p_i}{t_i})从大到小排序,当然(cmp)函数中可以直接使用上面的式子避免精度误差。

由于(frac{p_i}{t_i})相等的问题可以任意决定顺序,因此我们要求出每个问题完成的最早时间(L_i)和最迟时间(R_i)

二分答案

这道题显然可以二分答案。

我们重新把所有问题按照(p_i)的大小排序,那么就是要对于所有(i),满足不存在(j<i),使得(p_j<p_i)(p_j(T-cL_j)>p_i(T-cR_i))(显然(j)的最早时间和(i)的最迟时间肯定可以同时取等)。

因此只要维护好满足(p_j<p_i)(p_j(T-cL_j))的最大值(Mx)及满足(j<i)(p_j(T-cL_j))的最大值(Tx),只要当(p_{i-1}<p_i)的时候更新(Mx=Tx)即可。

代码:(O(nlogtexttt{eps}^{-1}))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 150000
#define LL long long
#define DB double
#define eps 1e-8
using namespace std;
int n;LL T;struct node {int p,t;LL L,R;I bool operator < (Con node& o) Con {return p<o.p;}}s[N+5];
I bool cmp(Con node& x,Con node& y) {return 1LL*x.p*y.t>1LL*y.p*x.t;}
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	char oc,FI[FS],*FA=FI,*FB=FI;
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
I bool Check(Con DB& c)//验证
{
	DB Mx,Tx=0;for(RI i=1;i<=n;Tx=max(Tx,s[i].p*(T-c*s[i].L)),++i)//Tx维护j<i的最大值
		if((i==1||s[i-1]<s[i])&&(Mx=Tx),Mx>s[i].p*(T-c*s[i].R)) return 0;return 1;//Mx维护p[j]<p[i]的最大值,和当前比较检验
}
int main()
{
	RI i;LL t,tt;for(read(n),i=1;i<=n;++i) read(s[i].p);for(i=1;i<=n;++i) read(s[i].t);sort(s+1,s+n+1,c++mp);//按p[i]/t[i]从大到小排序
	for(tt=0,i=1;i<=n;++i) (i==1||cmp(s[i-1],s[i]))&&(t=tt),tt+=s[i].t,s[i].L=t+s[i].t;//求出最早时间
	for(T=tt,i=n;i>=1;--i) (i==n||cmp(s[i],s[i+1]))&&(t=tt),tt-=s[i].t,s[i].R=t;//求出最迟时间
	DB l=0,r=1,mid;sort(s+1,s+n+1);W(r-l>eps) Check(mid=(l+r)/2)?l=mid:r=mid;return printf("%.8lfn",l),0;//二分答案
}

程序员灯塔
转载请注明原文链接:【CF639E】Bear and Paradox(贪心+二分)
喜欢 (0)