这道题数据量很小,所以用前缀和直接暴力解决了
首先将浮点数转换为整数;
int_p=(int)(dou_p*100+0.5); 必须加一个eps,否则浮点数运算会有误差
然后从高到低枚举
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=1e6+7; 5 const int M=5007; 6 struct node { 7 bool by; 8 int p; LL num; 9 }; 10 node t[M]; 11 bool flag[M]; 12 LL sum1[N], sum2[N]; 13 int main () 14 { 15 string str; int i=0,p_max=0,p_min=0x3f3f3f3f; 16 while (cin>>str) { 17 i++; 18 if (str[0]=='c') { int x; cin>>x; flag[x]=1; } 19 else { 20 double p; 21 cin>>p>>t[i].num; 22 if (str[0]=='b') t[i].by=1; 23 t[i].p=(int)(p*100+0.5); 24 p_max=max (p_max,t[i].p); 25 p_min=min (p_min,t[i].p); 26 } 27 } 28 int n=i; 29 for (i=1;i<=n;i++) 30 if (!flag[i]) { 31 if (t[i].by) sum1[t[i].p]+=t[i].num; 32 else sum2[t[i].p]+=t[i].num; 33 } 34 for (int i=1;i<N;i++) { 35 sum1[i]+=sum1[i-1]; 36 sum2[i]+=sum2[i-1]; 37 } 38 LL sum=0; int ans; 39 for (int i=p_max;i>=p_min;i--) { 40 LL x=min (sum1[N-1]-sum1[i-1],sum2[i]); 41 if (x>sum) { sum=x; ans=i; } 42 } 43 int a1=ans/100,a2=ans%100; 44 printf("%d.%02d %lld ",a1,a2,sum); 45 return 0; 46 }