http://codeforces.com/contest/268/problem/E
这道题的关键在于要提前排序 假设有两个相邻的顺序为
(l1,p1) (l2,p2)
这样的话时间为 四种可能性的和
1,(l1+l2)*p1*p2
2,(2*l1+l2)*p1*(1-p2)
3,(l1+l2)*(1-p1)*p2
4,(l1+l2)*(1-p1)*(1-p2)
相反顺序的话 (l2,p2) (l1,p1)
1,(l2+l1)*p1*p2
2,(2*l2+l1)*p2*(1-p1)
3,(l2+l1)*(1-p2)*p1
4,(l2+l1)*(1-p2)*(1-p1)
第一种顺序是我们选择的所有要大于第二中顺序 经过化简得
l1*(p1-p1*p2)>l2*(p2-p1*p2)
这个就是排序的函数
排序后从头到尾搜一遍 根据概率计算总时间
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<map> #include<vector> #include<stack> #include<set> #include<map> #include<queue> #include<algorithm> #include<cmath> #define LL long long //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int INF=0x3f3f3f3f; //const int MOD=1000000009; const int N=50005; struct node { int l; double p; }mem[N]; double t[N]; bool cmp(node x,node y) { return (x.l*(x.p-x.p*y.p)>y.l*(y.p-x.p*y.p)); } int main() { //freopen("data.in","r",stdin); int n; while(cin>>n) { for(int i=1;i<=n;++i) { cin>>mem[i].l>>mem[i].p; mem[i].p=mem[i].p/100.0; } sort(mem+1,mem+n+1,cmp); t[0]=0.0; double ans=0.0; for(int i=1;i<=n;++i) { t[i]=mem[i].l*mem[i].p+t[i-1]; ans+=(mem[i].l*mem[i].p+(1.0-mem[i].p)*(t[i-1]+mem[i].l)); } printf("%.9lf\n",ans); } return 0; }