您当前位置：首页 > php框架 > codeigniter > Codeforces 467E Alex and Complicated Task(高效)

Codeforces 467E Alex and Complicated Task(高效)

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

题目链接：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;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 一段超实用的12306刷票脚本

下一篇 SPOJ - DISUBSTR Distinct Substrings(后缀数组求不相同的子串个数)

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点