Music in Car CodeForces - 746F

2018-06-17 21:53:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Music in Car CodeForces - 746F

题意很难懂啊...

题意:http://blog.csdn.net/a838502647/article/details/74831793

题意是说找出一个连续区间,使得区间内所有a值之和最大。对区间的要求:区间内可以选出最多k个b值(题目用的是t,但是我换成了b)减去一半(如果b是奇数就减去(b-1)/2,偶数就减去b/2),要求减完后所有b值之和不超过w。

方法:

连续区间,所以尺取(two pointers?),就是实现方法感觉好...好糟糕...

显然,对于某个确定的区间,要选出其中b最大的k个数(如果整个区间都没有k个就是全部)减半。这样对于这个区间最好。

那么,如果现在检查到了满足条件的区间[l,r],然后进一步检查到了[l+1,r],那么当前区间显然仍然是合法的(消耗时间一定减少了);r显然可以直接继续向右扩展,而不用从l+1开始遍历检查。

那么,用一个数组c记录每个b能减去的值(其实可以不用,这里只是为了方便);维护两个数组,一个q1记录当前区间中c最大的k个值,另一个q2记录当前区间剩下的c;另开一些变量记录当前区间b总和与能减去的c总和,还有愉悦值总和。只需要在区间两端进行插入或删除操作,这样每次操作都只需要进行少量的更新以维护数组、变量。

由于需要动态求数组的最大、最小值,可以用set。和需要手动维护。

set操作方法:

(插入/删除的数据为X(pair<int(c值),int(编号)>))

当在区间右侧加入时:
如果q1的size小于k,那么直接插入q1;
否则,如果q1最小的小于X,那么将q1最小的取出放入q2,将X放入q1。

当在区间左侧删除时:
如果q1的size为0,那么不删除;
否则:
如果q1最小的大于X,那么在q2中删除,否则在q1中删除;
**曾经忘记:如果在q1中删除的且q2的size大于0那么从q2中取出最大的放入q1。

别人的代码(好看多了):http://www.cnblogs.com/y119777/p/6204515.html

  1 #include<cstdio>
  2 #include<set>
  3 using namespace std;
  4 typedef pair<int,int> P;
  5 set<P> q1,q2;//q1当前区间的被减半的,q2当前区间剩余的
  6 int l=1,r=0,n,w,k,sum1,sum2,sum3,ans;
  7 //当前区间:sum2当前区间时间总和,sum1被减半的量,sum3总愉悦值
  8 int a[200100],b[200100],c[200100];//c就是减去的量
  9 int main()
 10 {
 11     bool fl;
 12     int i;
 13     scanf("%d%d%d",&n,&w,&k);
 14     for(i=1;i<=n;i++)
 15         scanf("%d",&a[i]);
 16     for(i=1;i<=n;i++)
 17         scanf("%d",&b[i]),c[i]=b[i]/2;
 18     P X,Y;
 19     while(l<=n)
 20     {
 21         fl=false;
 22         while(fl==false&&r<n)
 23         {
 24             X=P(c[r+1],r+1);
 25             if(q1.size()<w)
 26             {
 27                 if(sum2-sum1+b[r+1]-c[r+1]<=k)//如果插入后时间不超过k
 28                 {
 29                     r++;
 30                     q1.insert(X);
 31                     sum2+=b[r];
 32                     sum1+=c[r];
 33                     sum3+=a[r];
 34                 }
 35                 else
 36                     fl=true;//如果插入后时间超过k了,就不能插入了
 37             }
 38             else
 39             {
 40                 Y=*q1.begin();
 41                 if(Y<X)
 42                 {
 43                     if(sum2+b[r+1]-(sum1-Y.first+X.first)<=k)//如果插入后时间不超过k
 44                     {
 45                         r++;
 46                         q2.insert(*q1.begin());
 47                         q1.erase(q1.begin());
 48                         q1.insert(X);
 49                         sum2+=b[r];
 50                         sum1=sum1-Y.first+X.first;
 51                         sum3+=a[r];
 52                     }
 53                     else
 54                         fl=true;
 55                 }
 56                 else
 57                 {
 58                     if(sum2+b[r+1]-sum1<=k)//如果插入后时间不超过k
 59                     {
 60                         r++;
 61                         q2.insert(X);
 62                         sum2+=b[r];
 63                         sum3+=a[r];
 64                     }
 65                     else
 66                         fl=true;
 67                 }
 68             }
 69         }
 70         ans=max(ans,sum3);
 71         if(q1.size()>0)
 72         {
 73             X=P(c[l],l);
 74             Y=*q1.begin();
 75             if(Y>X)
 76             {
 77                 q2.erase(X);
 78                 sum2-=b[l];
 79                 sum3-=a[l];
 80             }
 81             else
 82             {
 83                 q1.erase(X);
 84                 sum2-=b[l];
 85                 sum3-=a[l];
 86                 sum1-=c[l];
 87                 if(q2.size()>0)
 88                 {
 89                     Y=*q2.rbegin();
 90                     q1.insert(Y);
 91                     sum1+=Y.first;
 92                     q2.erase(Y);
 93                 }
 94             }
 95         }
 96         l++;
 97     }
 98     printf("%d",ans);
 99     return 0;
100 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Qt--自定义View

下一篇:typedef