首页 > 代码库 > Codeforces 722C Destroying Array（并查集）*
Codeforces 722C Destroying Array（并查集）*
题目链接：http://codeforces.com/problemset/problem/722/C
题意：
有 n 个正整数序列。同时 n 个摧毁序列，从 1 到 n每次把正整数序列里对应下标的数字去掉，成为一个间隔。
问每去掉一个数字，序列中最大的连续子段和。
思路：
倒着想，这道题就变成了：从 n 到 1每次出现一个数字，若数字的两边已经存在集合，则把存在的集合合并为一个，
并更新集合的和，否则单独为一个集合。过程中始终维护序列中目前所有集合里和的最大值。
代码：
#include <iostream>#include <stdio.h>#include <cstring>#include <map>#include <queue>#include <set>#include <cmath>#include <time.h>#include <cstdlib>#include <algorithm>#define lson (i<<1)#define rson (lson|1)using namespace std;typedef long long LL;const int N = 100007;const int INF = 0x7fffffff;int pre[N], isR[N], n, num[N], pos[N], cnt_ans;LL val[N], ans[N], maxN;int find(int x){ if (pre[x] == x) return x; else return pre[x] = find(pre[x]);}void merge(int x, int y){ int fx = find(x); int fy = find(y); if (fx != fy) { pre[fx] = fy; isR[fx] = 0; val[fy] += val[fx]; if (val[fy] > maxN) maxN = val[fy]; }}int main(){ while (scanf("%d", &n) != EOF) { ans[0] = 0; cnt_ans = 1; for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); pre[i] = i; isR[i] = 0; val[i] = (LL)num[i]; } for (int i = 1; i <= n; i++) scanf("%d", &pos[i]); maxN = -1; for (int i = n; i > 0; i--) { isR[pos[i]] = 1; if (val[pos[i]] > maxN) maxN = val[pos[i]]; if (pos[i] + 1 <= n && isR[find(pos[i]+1)]) merge(pos[i], pos[i] + 1); if (pos[i] - 1 > 0 && isR[find(pos[i]-1)]) merge(pos[i] - 1, pos[i]); ans[cnt_ans++] = maxN; } for (int i = cnt_ans - 2; i >= 0; i--) printf("%lld\n", ans[i]); }}
Codeforces 722C Destroying Array（并查集）*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。