博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF Covered Path (贪心)
阅读量:6404 次
发布时间:2019-06-23

本文共 2152 字,大约阅读时间需要 7 分钟。

Covered Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The on-board computer on Polycarp's car measured that the car speed at the beginning of some section of the path equals v1 meters per second, and in the end it is v2 meters per second. We know that this section of the route took exactly t seconds to pass.

Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value (i.e., the difference in the speed of any two adjacent seconds does not exceed d in absolute value), find the maximum possible length of the path section in meters.

Input

The first line contains two integers v1 and v2 (1 ≤ v1, v2 ≤ 100) — the speeds in meters per second at the beginning of the segment and at the end of the segment, respectively.

The second line contains two integers t (2 ≤ t ≤ 100) — the time when the car moves along the segment in seconds, d (0 ≤ d ≤ 10) — the maximum value of the speed change between adjacent seconds.

It is guaranteed that there is a way to complete the segment so that:

  • the speed in the first second equals v1,
  • the speed in the last second equals v2,
  • the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d.
Output

Print the maximum possible length of the path segment in meters.

Sample test(s)
input
5 6 4 2
output
26
input
10 10 10 0
output
100 哈哈,终于可以完全理解的A出一道贪心题了。假设每个点的速度是V,剩余的时间是T_S,加速量是X,那么需要满足 V + X <= V_2 + T_S * d,以此来更新每个点的速度就行。
1 #include 
2 #include
3 using namespace std; 4 5 int main(void) 6 { 7 int v_1,v_2,t,d; 8 int sum = 0; 9 10 cin >> v_1 >> v_2;11 cin >> t >> d;12 sum += v_1;13 14 int v = v_1;15 for(int i = 2;i <= t;i ++)16 for(int j = d;j >= -d;j --)17 if(v + j <= v_2 + (t - i) * d)18 {19 v += j;20 sum += v;21 break;22 }23 cout << sum << endl;24 25 return 0;26 }

 

转载于:https://www.cnblogs.com/xz816111/p/4442864.html

你可能感兴趣的文章
MySQL常见错误代码及代码说明
查看>>
Cglib动态代理基础使用
查看>>
设计模式 - 单例模式
查看>>
react native参考资料
查看>>
技术人员,为什么会苦逼
查看>>
使用126邮箱发送邮件的python脚本
查看>>
关于IP SLA及与EEM联动的探讨(转)
查看>>
DHCP在VLAN中的端口
查看>>
Maven
查看>>
课后习题和问题 Chapter 2 Problems 10-18
查看>>
缓存系统在游戏业务中的特异性
查看>>
Ngrok搭建自己的内网穿透
查看>>
在高性能的IO体系设计中,有几个名词概念常常会使我们感到迷惑不解。具体如下:...
查看>>
聊聊Java并发面试问题之公平锁与非公平锁是啥?
查看>>
linux cron计划任务
查看>>
针对nginx应用场景的配置 知识整理
查看>>
delegate、notification、KVO场景差别
查看>>
HDOJ 1166.敌兵布阵
查看>>
SQL Server性能优化(8)堆表结构介绍
查看>>
Opencv关于滑动条bar操作的实例
查看>>