首页 > 代码库 > C. Destroying Array 并查集，逆向思维
C. Destroying Array 并查集，逆向思维
用并查集维护线段，从后往前枚举没个删除的位置id[i]
那么，现在删除了这个，就是没有了的，但是上一个id[i + 1]就是还没删除的。
然后现在进行合并
int left = id[i + 1];(相当于每次都加入一个元素a[left])
它在这个位置，如果能和左右的合并，就是左右邻居都有元素，那么当然是合并最好，因为元素都是大于0的，越长越好。
合并的时候再记录一个数组sum[pos]表示以这个为根的总和是多少。
按并查集的思路更新整个并查集即可、
注意一点的就是，
要求ans[i]
那么ans[i + 1]是在没有id[i + 1]这个元素的前提下的最大值，现在有了这个元素，但是不见得会变大。
所以
ans[i] = max(ans[i + 1], sum[find(id[i + 1)]);
要和前一个比较一下
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 100000 + 20;int fa[maxn];LL sum[maxn];int find(int u) { if (fa[u] == u) return fa[u]; else return fa[u] = find(fa[u]);}void merge(int x, int y) { x = find(x); y = find(y); if (x != y) { fa[y] = x; sum[x] += sum[y]; }}int a[maxn];int id[maxn];bool has[maxn];LL ans[maxn];void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) fa[i] = i; for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) scanf("%d", &id[i]); ans[n] = 0; for (int i = n - 1; i >= 1; --i) { int left = id[i + 1]; sum[left] = a[left]; if (has[left + 1]) { merge(left, left + 1); } if (has[left - 1]) { merge(left, left - 1); } ans[i] = max(ans[i + 1], sum[find(left)]); has[left] = 1; } for (int i = 1; i <= n; ++i) { printf("%I64d\n", ans[i]); }}int main() {#ifdef local freopen("data.txt","r",stdin);#endif work(); return 0;}
C. Destroying Array 并查集，逆向思维
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。