codeforces 355C - Vasya and Robot
2024-08-25 17:08:44
因为在允许的情况下,必然是左右手交替进行,这样不会增加多余的无谓的能量。
然后根据不同的分界点,肯定会产生左手或右手重复使用的情况,这是就要加上Qr/Ql * 次数。
一开始的想法,很直接,枚举每个分界点,计算出总共要用的能量,取最小的那个即是答案:
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n,l,r,Q_l,Q_r,w[+];
scanf("%d%d%d%d%d",&n,&l,&r,&Q_l,&Q_r);
for(int i=;i<=n;i++) scanf("%d",&w[i]); int ans=,left_enegry_sum,right_enegry_sum;
for(int m=;m<=n;m++) //边界在m右边
{
left_enegry_sum=,right_enegry_sum=;
for(int i=;i<=m;i++) left_enegry_sum+=w[i]*l;
for(int i=n;i>m;i--) right_enegry_sum+=w[i]*r;
if(m < n-m) //右手拿的东西多
right_enegry_sum += ( (n-m) - m - ) * Q_r;
else if(m > n-m) //左手拿的东西多
left_enegry_sum += ( m - (n-m) - ) * Q_l;
ans=min(ans , left_enegry_sum + right_enegry_sum);
//printf("now:\n\tleft_enegry_sum=%d\tright_enegry_sum=%d\tenegry_sum=%d\n",left_enegry_sum,right_enegry_sum,ans);
}
printf("%d\n",ans);
}
但是在数据来那个很大的情况下会超时。
所以考虑到我们的枚举分界点方向是从左到右,那么我们不需要每次枚举分界点都O(n)地去计算左右手拿物品的能量
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n,l,r,Q_l,Q_r,w[+];
scanf("%d%d%d%d%d",&n,&l,&r,&Q_l,&Q_r);
for(int i=;i<=n;i++) scanf("%d",&w[i]); w[]=; int ans=,left_energy_sum=,right_energy_sum=;
for(int i=;i<=n;i++) right_energy_sum+=w[i]*r;
for(int m=;m<=n;m++) //边界在m右边
{
left_energy_sum+=w[m]*l; //分界点右移一位,left_enrgy_sum增加新增的那一个物品消耗的能量即可
right_energy_sum-=w[m]*r; //分界点右移一位,right_enrgy_sum减少那一个物品消耗的能量即可
if(m < n-m) //右手拿的东西多
ans=min(ans , left_energy_sum + right_energy_sum + ( (n-m) - m - ) * Q_r);
else if(m > n-m) //左手拿的东西多
ans=min(ans , left_energy_sum + ( m - (n-m) - ) * Q_l + right_energy_sum);
else //两只手拿的一样多
ans=min(ans , left_energy_sum + right_energy_sum);
//printf("now:\n\tleft_energy_sum=%d\tright_energy_sum=%d\tenergy_sum=%d\n",left_energy_sum,right_energy_sum,ans);
}
printf("%d\n",ans);
}
最新文章
- VO对象和PO对象的区别
- 20.SqlServer中if跟循环语句
- c++ 指针(一)
- offsetleft、offsetTop、offsetParent的兼容性问题
- 中断处理流程,ok6410
- knockout 学习实例3 html
- 使用wkhtmltopdf实现HTML转PDF的解决方案
- java_ant详解
- 神奇的NOIP模拟赛 T3 LGTB 玩THD
- c++中的vector原理
- Ancient Message (古埃及象形文字识别 Uva 1103)
- UESTC_温泉旅店 CDOJ 878
- 仿360新闻的热搜图片,win8风格随机九宫格布局
- 【android studio】 gradle配置成本地离线zip包
- HMAC-SHA256 签名方法各个语音的实现方式之前端JavaScriptes6
- 论文笔记:AdaScale: Towards real-time video object detection using adaptive scalingAdaScale
- MySQL9:索引实战
- 飞机躲避炮弹---java
- iOS pods编译原理
- JavaScript(JS)简介