題目鏈接：Codeforces 467E Alex and Complicated Task
題目大意：給定一個長度為n序列，然后從中挑選盡量多的4元組（不能重疊）。
解題思路：每次找的四元組的左端肯定是要盡量小的。所以用一個單調棧維護，如果新加入的數x在棧中出現過，那么就將兩個數之間的數標記為在x。如果一個數的標記不為空，就意味著找到對應的四元組。有因為序列是從左遍歷過去的，所以找到的一定是最優的。
#include <cstdio>
#include <cstring>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 5 * 1e5 + 5;
int N, B[maxn];
void solve () {
vector<int> ans;
map<int, int> pre, sum;
int mv = 0;
while (mv < N) {
pre.clear();
sum.clear();
stack<int> sta;
for (int& i = mv; i < N; i++) {
if (pre[B[i]]) {
for (int j = 0; j < 2; j++) {
ans.push_back(pre[B[i]]);
ans.push_back(B[i]);
}
break;
}
while (!sta.empty() && (sum[B[i]] > 1 || (sum[B[i]] == 1 && sta.top() != B[i]))) {
pre[sta.top()] = B[i];
sum[sta.top()]--;
sta.pop();
}
sta.push(B[i]);
sum[B[i]]++;
}
mv++;
}
printf("%lu
", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d%c", ans[i], i == ans.size() - 1 ? '
' : ' ');
}
int main () {
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &B[i]);
solve();
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
