Codeforces Round#768(Div.2) E. Paint the Middle

本文主要是介绍Codeforces Round#768(Div.2) E. Paint the Middle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给定编号从 1 到 n的 n 个元素，元素 i 具有值 ai 和颜色 ci，最初,对于所有 i，ci=0。
可以应用以下操作:
选取三个元素i、j、k（1≤i<j<k≤n），使得ci、cj、ck都等于0且ai=ak，则令cj =1。
问$max\sum ci$为多少

题解：

可以将这题看成区间覆盖的问题，只要两头有个相同的数显然可以将中间所有的ci变为1.所以我们只需要预处理所有的数出现最后一次的位置，然后判断当前的i是否在这个以a[i]为左端点的区间内，如果是则答案数+1，反之贪心的选择一个最右的端点;

#include<bits/stdc++.h>
using namespace std;
int a[200005], ed[200005];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];ed[a[i]] = i;}int cover = 0,r=0,res=0;for (int i = 1; i <= n; i++){r = max(r, ed[a[i]]);if (cover > i)res++;else cover = r;}cout << res << endl;
}

这篇关于Codeforces Round#768(Div.2) E. Paint the Middle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---