网站建站的标准,成都软件外包开发,抚州网站制作,mvc 手机网站开发Description Input 第一行两个正整数N、S#xff0c;分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行#xff0c;第K 行三个实数AK、BK、RateK#xff0c;意义如题目中所述Output 只有一个实数MaxProfit#xff0c;表示第N 天的操作结束时能够获得的最大的金钱…Description Input 第一行两个正整数N、S分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行第K 行三个实数AK、BK、RateK意义如题目中所述 Output 只有一个实数MaxProfit表示第N 天的操作结束时能够获得的最大的金钱 数目。答案保留3 位小数。 Sample Input 3 100 1 1 1 1 2 2 2 2 3 Sample Output 225.000 HINT 测试数据设计使得精度误差不会超过10-7。 对于40%的测试数据满足N ≤ 10 对于60%的测试数据满足N ≤ 1 000 对于100%的测试数据满足N ≤ 100 000 1 #include iostream2 #include cstring3 #include cstdio4 #include algorithm5 using namespace std;6 const double eps1e-8;7 const int maxn100010;8 struct Node{9 double a,b,r,x,y,k;
10 int id;
11 }d[maxn],t[maxn];
12 double f[maxn];
13 int st[maxn],cnt,n;
14 double Abs(double a){return a0?a:-a;}
15 double K(int a,int b){
16 if(Abs(d[a].x-d[b].x)eps)return 1e20;
17 return (d[a].y-d[b].y)/(d[a].x-d[b].x);
18 }
19 void Solve(int l,int r){
20 if(lr){
21 f[l]max(f[l],f[l-1]);
22 d[l].yf[l]/(d[l].r*d[l].ad[l].b);
23 d[l].xd[l].y*d[l].r;
24 return;
25 }
26 int mid(lr)1,t1l,t2mid1;
27 for(int il;ir;i){
28 if(d[i].idmid)
29 t[t1]d[i];
30 else
31 t[t2]d[i];
32 }
33 for(int il;ir;i)d[i]t[i];
34 Solve(l,mid);
35 cnt0;
36 for(int il;imid;i){
37 while(cnt1K(i,st[cnt])-K(st[cnt],st[cnt-1])eps)cnt--;
38 st[cnt]i;
39 }
40 int fir1;
41 for(int imid1;ir;i){
42 while(fircntK(st[fir1],st[fir])-d[i].keps)fir;
43 f[d[i].id]max(f[d[i].id],d[st[fir]].x*d[i].ad[st[fir]].y*d[i].b);
44 }
45 Solve(mid1,r);
46 t1l;t2mid1;
47 for(int il;ir;i){
48 if(t2r1||(d[t2].x-d[t1].xeps||Abs(d[t2].x-d[t1].x)epsd[t2].y-d[t1].yeps)t1mid)
49 t[i]d[t1];
50 else
51 t[i]d[t2];
52 }
53 for(int il;ir;i)
54 d[i]t[i];
55 }
56
57
58 bool cmp(Node a,Node b){
59 return a.kb.k;
60 }
61 int main(){
62 scanf(%d%lf,n,f[1]);
63 for(int i1;in;i){
64 scanf(%lf%lf%lf,d[i].a,d[i].b,d[i].r);
65 d[i].k-d[i].a/d[i].b;
66 d[i].idi;
67 }
68 sort(d1,dn1,cmp);
69 Solve(1,n);
70 printf(%.3lf\n,f[n]);
71 return 0;
72 } 这里还有Splay。 1 #include iostream2 #include cstring3 #include cstdio4 using namespace std;5 const double eps1e-8;6 const double INF1e20;7 const int maxn100010;8 int ch[maxn][2],fa[maxn],rt,tot,n;9 double X[maxn],Y[maxn],lk[maxn],rk[maxn],ans;10 double fabs(double x){return (x0)?x:-x;}11 void Rotate(int x){12 int yfa[x],gfa[y],cch[y][1]x;13 ch[y][c]ch[x][c^1];fa[ch[y][c]]y;14 ch[x][c^1]y;fa[y]x;fa[x]g;15 if(g)ch[g][ch[g][1]y]x;16 }17 18 void Splay(int x,int g0){19 for(int y;(yfa[x])!g;Rotate(x))20 if(fa[y]!g)Rotate((ch[fa[y]][1]y)(ch[y][1]x)?y:x);21 if(!g)rtx; 22 }23 24 double Get_K(int j,int k){25 if(fabs(X[j]-X[k])eps)return INF;26 else return (Y[j]-Y[k])/(X[j]-X[k]);27 }28 29 int Get_Prev(){30 int pch[rt][0],retp;31 while(p){32 if(Get_K(rt,p)epslk[p])pch[p][0];33 else retp,pch[p][1];34 }35 return ret;36 }37 38 int Get_Succ(){39 int pch[rt][1],retp;40 while(p){41 if(Get_K(p,rt)rk[p]eps)pch[p][1];42 else retp,pch[p][0];43 }44 return ret;45 }46 47 void Insert(int r,int pre,int p){48 if(r0){rp;fa[p]pre;return;}49 if(X[p]X[r]eps)Insert(ch[r][0],r,p);50 else Insert(ch[r][1],r,p);51 }52 53 void Update(int p){54 Splay(p);55 if (ch[p][0]){56 int lGet_Prev();57 Splay(l,p);ch[l][1]0;58 lk[p]rk[l]Get_K(p,l);59 }60 else lk[p]INF;61 if (ch[p][1]){62 int rGet_Succ();63 Splay(r,p); ch[r][0]0;64 rk[p]lk[r]Get_K(r,p);65 }66 else rk[p]-INF;67 if (lk[p]rk[p]eps){68 rtch[p][0]; ch[rt][1]ch[p][1]; fa[ch[p][1]]rt; fa[rt]0;69 rk[rt]lk[ch[p][1]]Get_K(ch[rt][1],rt);70 }71 } 72 73 int Get_Pos(double k){74 int prt;75 while(p){76 if(lk[p]epskkepsrk[p])break;77 if(lk[p]keps)pch[p][0];78 else pch[p][1];79 }80 return p;81 }82 83 double Get_Ans(double a,double b){84 int pGet_Pos(-b/a);85 return a*Y[p]b*X[p];86 }87 88 int main(){89 #ifndef ONLINE_JUDGE90 freopen(cash.in,r,stdin);91 freopen(cash.out,w,stdout);92 #endif93 double a,b,rate;94 scanf(%d%lf,n,ans);95 for(int i1;in;i){96 scanf(%lf%lf%lf,a,b,rate);97 if(i!1)ansmax(ans,Get_Ans(a,b));98 X[i]ans/(rate*ab);99 Y[i]X[i]*rate;
100 Insert(rt,0,i);
101 Update(i);
102 }
103 printf(%.3f\n,ans);
104 return 0;
105 } 转载于:https://www.cnblogs.com/TenderRun/p/5307998.html
