Music in Car CodeForces - 746F
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
#include<cstdio>
#include<set>
using namespace std;
typedef pair<int,int> P;
set<P> q1,q2;//q1当前区间的被减半的,q2当前区间剩余的
int l=,r=,n,w,k,sum1,sum2,sum3,ans;
//当前区间:sum2当前区间时间总和,sum1被减半的量,sum3总愉悦值
int a[],b[],c[];//c就是减去的量
int main()
{
bool fl;
int i;
scanf("%d%d%d",&n,&w,&k);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n;i++)
scanf("%d",&b[i]),c[i]=b[i]/;
P X,Y;
while(l<=n)
{
fl=false;
while(fl==false&&r<n)
{
X=P(c[r+],r+);
if(q1.size()<w)
{
if(sum2-sum1+b[r+]-c[r+]<=k)//如果插入后时间不超过k
{
r++;
q1.insert(X);
sum2+=b[r];
sum1+=c[r];
sum3+=a[r];
}
else
fl=true;//如果插入后时间超过k了,就不能插入了
}
else
{
Y=*q1.begin();
if(Y<X)
{
if(sum2+b[r+]-(sum1-Y.first+X.first)<=k)//如果插入后时间不超过k
{
r++;
q2.insert(*q1.begin());
q1.erase(q1.begin());
q1.insert(X);
sum2+=b[r];
sum1=sum1-Y.first+X.first;
sum3+=a[r];
}
else
fl=true;
}
else
{
if(sum2+b[r+]-sum1<=k)//如果插入后时间不超过k
{
r++;
q2.insert(X);
sum2+=b[r];
sum3+=a[r];
}
else
fl=true;
}
}
}
ans=max(ans,sum3);
if(q1.size()>)
{
X=P(c[l],l);
Y=*q1.begin();
if(Y>X)
{
q2.erase(X);
sum2-=b[l];
sum3-=a[l];
}
else
{
q1.erase(X);
sum2-=b[l];
sum3-=a[l];
sum1-=c[l];
if(q2.size()>)
{
Y=*q2.rbegin();
q1.insert(Y);
sum1+=Y.first;
q2.erase(Y);
}
}
}
l++;
}
printf("%d",ans);
return ;
}
最新文章
- sonar的安装与代码质量检测实例
- 6、XML(2)
- shell script创建库
- MySQL类型转换
- sql2008还原问题
- 程序员带你学习安卓开发系列-Android文件存储
- ashx一般处理程序文件用处
- Hibernate Validation各注解的用法
- 操作系统的页面置换C++算法:OPT FIFO LRU CLOCK 计算缺页率
- C strstr() 函数
- ASP.Net MVC View
- erlang ets表
- JVM 参数设置
- vue组件局部与全局注册的区别
- 常用的OO设计原则
- 海量日志实时收集系统架构设计与go语言实现
- 如何在windows下使用pip安装
- Failed to import package with error: Couldn&#39;t decompress package的解决方案
- 洛谷P2312 解方程 [noip2014] 数论
- JBDC—③数据库连接池的介绍、使用和配置
热门文章
- zabbix基于SNMP 协议监控路由器
- Android 代码写控件
- Pattern: Microservice Architecture
- gitlab merge过程
- poj 1179 $Polygon$(断环成链)
- myeclipse -vmargs -Xmx512m -XX:MaxPermSize=256m -XX:ReservedCodeCacheSize=64m
- dede摘要长度,dedecms摘要限制,dedecms摘要字数
- codeforces 441C. Valera and Tubes 解题报告
- 【前端】Nodejs给没有引号的json数据添加引号
- AndroidStudio修改主题外观和字体大小