【解题报告】Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)

题目链接

A. Andryusha and Socks（Codeforces 782A）

思路

用一个支持高效查找和删除的数据结构（比如二叉搜索树）维护桌上的袜子就好了，而 $STL$ 中的 $set$ 容器正好能满足这个需求。

代码

#include 
using namespace std;set <int> s;
int n, a, ans;int main() {
//    freopen("Input2.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cin >> n;for(int i = 1; i <= 2 * n; i++) {cin >> a;if(s.count(a)) {s.erase(a);}else {s.insert(a);}ans = max(ans, (int)s.size());}cout << ans << endl;return 0;
}

B. The Meeting Place Cannot Be Changed（Codeforces 782B）

思路

这题看问题类型和数据规模就很像二分查找。于是自然往这个方面想。
显然，如果要二分查找的话肯定查找的是最小的时间 $t_{min}$ ，那么自然而然，问题转化为如何判定在给定的时间t内是否能让所有人聚集到某点 $x$ 。应该注意到 $x$ 也是未知量，因为其连续性而且值的范围很大，所以也不好枚举。所以要将问题进一步转化。
对于某个人 $i$ 我们是可以轻易求出其在 $t$ 个单位的时间内的移动范围 $[l_i, r_i]$ 的，如果所有人的移动范围存在一个公共点，那么所有人就能在 t

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！