中国最全IT社区平台 联系我们 | 收藏本站
阿里云优惠
您当前位置:首页 > php框架 > codeigniter > Codeforces 467E Alex and Complicated Task(高效)

Codeforces 467E Alex and Complicated Task(高效)

来源:程序员人生   发布时间:2014-10-10 08:00:00 阅读次数:765次

题目链接: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; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
为码而活
积分:4222
12粉丝
7关注
热门话题
栏目热点