题目链接: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\n", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
}
int main () {
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &B[i]);
solve();
return 0;
}
分享到:
相关推荐
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 185A - Plant 全测试点49个
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation...
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
Some of the Codeforces problems codes
CodeForces :bar_chart: 使用Java
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...