題目鏈接：Codeforces 467E Alex and Complicated Task
題目大意：給定一個(gè)長度為n序列，然后從中挑選盡量多的4元組（不能重疊）。
解題思路：每次找的四元組的左端肯定是要盡量小的。所以用一個(gè)單調(diào)棧維護(hù)，如果新加入的數(shù)x在棧中出現(xiàn)過，那么就將兩個(gè)數(shù)之間的數(shù)標(biāo)記為在x。如果一個(gè)數(shù)的標(biāo)記不為空，就意味著找到對(duì)應(yīng)的四元組。有因?yàn)樾蛄惺菑淖蟊闅v過去的，所以找到的一定是最優(yōu)的。
#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網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
