CodeForces 240D  D. Merging Two Decks  解题报告  贪心

题目意思看了好久，最后终于看明白了，给两摞牌，一摞n张，另一罗m张，分别编号1--n,n+1--n+m;  然后每张牌有0,1两种状态，希望合并成一摞； 规则是相对顺序不变，即同一罗中序号小的在上面，不同一罗在不管； 最后再翻转，规则是，翻转top到第i个，整个翻转，最后都是0状态既可以了……

就是两种状态，第一次合并的时候，要么是0在最上面，要么是1在最上面，然后为了以后翻转的次数尽可能的少，那么尽量相同的状态在一起，然后再翻转 什么时候翻转呢？ 相邻的想个不相同就翻转，记录两种翻转次数，记录一个小的就好了；     因为最上面只有两个可能0/1;   注意细节，在最后一个加上一个哨兵，避免最后全部翻转成111111……

代码是CF上的，直到把代码读懂，才明白题意……

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int A[200005];
int V[200005];
int N, M;
vector<int> solve(int type)
{
    int K = 0, x = 1, y = N + 1;
    while (x <= N || y <= N + M)
    {
        while (x <= N && A[x] == type)
            V[K++] = x++;
        while (y <= N + M && A[y] == type)
            V[K++] = y++;
        type = 1 - type;///变换状态
    }

    /// 在该翻转的时候就翻转，相邻的两个不一样就翻转；在最后的后一步加一个哨兵0；防止……
    vector<int> answer;
    for (int i = 0; i < N + M; ++i)
        if (A[V[i]] != A[V[i + 1]])  ///最后一个多一个哨兵
            answer.push_back(i + 1);
    return answer;
}

int main() {
    //ifstream cin("input.txt");
   // ofstream cout("output.txt");

    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    cin >> M;
    for (int i = N + 1; i <= N + M; ++i)
        cin >> A[i];


    vector<int> answer = solve(0);
    if (solve(1).size() <= answer.size())
        answer = solve(1);
     else answer = solve(0);


    ///V是最后一次调用slove的结果
    for (int i = 0; i < N + M; ++i)
        cout << V[i] << " ";
    cout << "\n";
///=================================================
    cout << answer.size() << "\n";
    for (int i = 0; i < int(answer.size()); ++i)
        cout << answer[i] << " ";
    cout << "\n";
}