[AtCoder][ARC082]Sandglass 题解
2018-08-02 05:43:43来源:博客园 阅读 ()
Sandglass
时间限制: 1 Sec 内存限制: 128 MB
原题链接 https://arc082.contest.atcoder.jp/tasks/arc082_d
题目描述
We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.
The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second. When the upper bulb no longer contains any sand, nothing happens.
Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X?a grams of sand (for a total of X grams).
We will turn over the sandglass at time r1,r2,..,rK. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.
You are given Q queries. Each query is in the form of (ti,ai). For each query, assume that a=ai and find the amount of sand that would be contained in bulb A at time ti.
Constraints
1≤X≤109
1≤K≤105
1≤r1
样例输入
180
3
60 120 180
3
30 90
61 1
180 180
样例输出
60
1
120
题解
我的做法是进行带优化的模拟,因为题目输入是确保后一个时间一定大于前一个时间的,所以对于翻转的模拟总共只需要按顺序进行一次便可,最后使用数学结论根据时间和初始质量推出答案。
需要特别注意的是,这道题会卡输入输出,如果不使用scanf/printf的话,必须要关闭同步锁且不能使用endl,不然会TLE。(可能是华东OJ的原因)
心疼那将近一半被输入输出卡掉的提交QAQ
代码
42 ms/1664 KB(AtCoder)
80 ms/2080 KB(华东 OJ)
#include <iostream> #include <algorithm> using namespace std; int x, k, q, t, a, low, up, add, delta, now, ans, r[100007]; bool flag; int cal(int tt, int lower = 0, int upper = x) { if (tt < lower) return lower; if (tt > upper) return upper; return tt; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cin >> x >> k; for (int i = 1; i <= k; i++) cin >> r[i]; cin >> q; low = x, now = 1; while (q--) { cin >> t >> a; while (t >= r[now] && now <= k) { delta = (flag ? 1 : -1) * (r[now] - r[now - 1]), add += delta; up = cal(delta + up), low = cal(delta + low); flag = !flag, now++; } ans = cal((flag ? 1 : -1) * (t - r[now - 1]) + cal(a + add, up, low)); cout << ans << '\n'; } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- AtCoder Beginner Contest 162(A~D) 2020-04-15
- AtCoder Beginner Contest 160(A~D) 2020-03-29
- AtCoder Grand Contest 043--A - Range Flip Find Route 2020-03-22
- AtCoder arc078_d Mole and Abandoned Mine 2020-02-17
- AtCoder agc007_d Shik and Game 2020-02-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash