luogu 3407 散步
2024-08-27 22:09:51
题目链接
题意
按从左到右的顺序给出数轴上的一群人,有人向左走,有人向右走,一旦两人相遇就会停在当前位置,后来走到该位置的人也会停在该位置。问经过一段时间这些人分别在什么位置。
思路
可以将这些人分为若干组,同一组中的人全部相向而行,呈>>><<<
的态势。这一组人最终的位置就取决于中间两个人的位置,只要知道他们有没有相遇,如果相遇在哪个点,其他所有人的位置都决定了。
再注意特判一下最左边一直向左走的人和最右边一直向右走的人即可。
时间复杂度\(O(n)\).
Code
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
LL p[maxn], t;
LL d[maxn];
LL max(LL a, LL b) { return a > b ? a : b; }
LL min(LL a, LL b) { return a < b ? a : b; }
LL n, q;
int main() {
scanf("%lld%lld%lld", &n, &t, &q);
for (LL i = 1; i <= n; ++i) scanf("%lld%lld", &p[i], &d[i]);
LL i = 1, j = n;
for (; i <= n; ++i) {
if (d[i] == 1) break;
p[i] -= t;
}
for (; j > 0; --j) {
if (d[j] == 2) break;
p[j] += t;
}
LL s = i, pos;
LL mid;
d[j+1] = 1;
for (; i <= j; ++i) {
if (d[i] == 1 && d[i+1] == 2) mid = p[i]+p[i+1] >> 1, pos = i+1;
else if (d[i] == 2 && d[i+1] == 1) {
for (LL k = s; k < pos; ++k) p[k] = min(p[k]+t, mid);
for (LL k = pos; k <= i; ++k) p[k] = max(p[k]-t, mid);
s = i+1;
}
}
while (q--) {
LL x;
scanf("%lld", &x);
printf("%lld\n", p[x]);
}
return 0;
}
最新文章
- 相关query挖掘
- signalr推送消息
- 使用HttpDownLoadHelper下载文件
- Spring MVC exception - Invoking request method resulted in exception : public static native long java.lang.System.currentTimeMillis()
- localStorage的使用
- 持续集成工具Hudson安装实例
- putExtra方法
- C#报错:创建调试信息文件 ……obj\Debug\model.pdb: 拒绝访问
- dalvik虚拟内存管理之二——垃圾收集
- POJ2251Dungeon Master
- Java基础知识强化之集合框架笔记12:Collection集合存储字符串并遍历
- e.target 和 e.srcElement 的使用问题
- 自动编译CoffeeScript的Gruntfile.js
- JS对url进行编码和解码(三种方式区别)
- How does exercise keep your brain young?
- [并查集+LCA USACO18OPEN ] Disruption
- Publisher和Subscriber节点
- 在oracle的连接(join)中使用using关键字
- AsyncTask应用示例
- 【Java】数组升序和降序