【二分】【动态规划】Codeforces Round #393 (Div. 1) B. Travel Card
水dp,加个二分就行,自己看代码。
2 seconds
256 megabytes
standard input
standard output
A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.
The fare is constructed in the following manner. There are three types of tickets:
- a ticket for one trip costs 20 byteland rubles,
- a ticket for 90 minutes costs 50 byteland rubles,
- a ticket for one day (1440 minutes) costs 120 byteland rubles.
Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.
To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.
You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.
The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.
Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.
Output n integers. For each trip, print the sum the passenger is charged after it.
3
10
20
30
20
20
10
10
13
45
46
60
103
115
126
150
256
516
20
20
10
0
20
0
0
20
20
10
In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10rubles only.
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100010],f[100010];
int main()
{
freopen("b.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+20;
int *p=lower_bound(a+1,a+n+1,a[i]-89);
f[i]=min(f[i],f[p-a-1]+50);
p=lower_bound(a+1,a+n+1,a[i]-1439);
f[i]=min(f[i],f[p-a-1]+120);
printf("%d\n",f[i]-f[i-1]);
}
return 0;
}
最新文章
- protocol的简单写法
- :after和:before炫酷用法总结
- JAVA操作MongoDB数据库
- Daily Scrum 10.25
- Android 圆形ProgressBar风格设置
- mysql中一对一,一对多,多对多关系
- Java 开发 gRPC 服务和客户端
- 对付ring0 inline hook
- 【POJ】【1067】取石子游戏
- Ubuntu12.04 + 虚拟机VMware 9 + Secure CRT + EditPlus 本地C++开发环境搭建
- [LeetCode] Single Number III ( a New Questions Added today)
- Altium自定义的快捷键设置
- C#多线程实践——线程同步
- java处理图片时找到不sun.awt.X11GraphicsEnvironment问题
- MVC 5 Scaffolding多层架构代码生成向导开源项目
- Java8之旅(七) - 函数式备忘录模式优化递归
- 2017ecjtu-summer training #5 UVA10382
- echarts的地图点击事件
- node,npm,vue的全局升级
- PHP 设置分页 可以直接引用 最下面有自己引用的方法和注释
热门文章
- bootstrap、angularJS、nodeJs、reactJs视频教程
- HNOI2002 彩票 [搜索]
- poj 2378 Tree Cutting 树形dp
- Robot POJ - 1376
- HDU 多校对抗 F Naive Operations
- 【BZOJ2460】【BJOI2011】元素 [线性基]
- NYOJ 349 Sorting It All Out (拓扑排序 )
- [bzoj3231][SDOI2008]递归数列——矩阵乘法
- bzoj 2435 BFS
- 【bzoj3744】GTY的妹子序列