题解：CF1784B Letter Exchange

· · 题解

CF1784B 题解

题目传送门

题目大意

有 3m 张纸条，分别写有 w，i，n，现在随机发给 m 个人，现在请进行次数最少的两两交换操作，使恰好每人手中是 win。

思路

采用一下映射，win 分别对应 1，2，3。

然后略微贪心的匹配一下，首先一定是的多 1 缺 2 与多 2 缺 1 的匹配（包括类似的），然后剩下的大概就是像样例中的一圈循环多 1 缺 2，多 2 缺 3，多 3 缺 1，或者多 1 缺 3，多 2 缺 1，多 3 缺 2，且只有这两种，把他们三个分为一组，一组只需要两次操作。

那么为了方便记录开一个二维 vector 一维记录多余，后一维记录所缺，注意到一人手中只有可能多于一个字符，但有可能缺两个字符，比如 www，要把它存在 vec[1][2] 与 vec[1][3]。记录之后模拟前面的操作就好了。

代码

代码长但是很多是复制粘贴。码风抽象，不必在意。

int main()
{
    scanf("%d", &ttt);
    while(ttt--)
    {
        b[1][2].clear(), b[2][1].clear(), b[1][3].clear(), b[3][1].clear(), b[2][3].clear(), b[3][2].clear();//多测清空
        scanf("%d", &m);
        char op;
        for(int i = 1; i <= m; i++)
        {
            int st1 = 0, st2 = 0, st3 = 0;
            for(int j = 1; j <= 3; j++)
            {
                cin >> op;
                if(op == 'w') st1++;
                if(op == 'i') st2++;
                if(op == 'n') st3++;
            }
            //记录所缺与所多
            if(st1 == 3) b[1][2].push_back(i), b[1][3].push_back(i);
            if(st2 == 3) b[2][1].push_back(i), b[2][3].push_back(i);
            if(st3 == 3) b[3][1].push_back(i), b[3][2].push_back(i);
            if((st1 == 1) && (st2 == 2)) b[2][3].push_back(i);
            if((st1 == 1) && (st3 == 2)) b[3][2].push_back(i);
            if((st2 == 1) && (st1 == 2)) b[1][3].push_back(i);
            if((st2 == 1) && (st3 == 2)) b[3][1].push_back(i);
            if((st3 == 1) && (st2 == 2)) b[2][1].push_back(i);
            if((st3 == 1) && (st1 == 2)) b[1][2].push_back(i);
        }
        string ans = "";//统计答案
        int cnt = 0;//记录操作次数
        int l12 = b[1][2].size(), l21 = b[2][1].size(), l13 = b[1][3].size(), l31 = b[3][1].size(), l23 = b[2][3].size(), l32 = b[3][2].size();
        //第一层模拟[2][1]与[1][2]
        int ww = min(l12, l21);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[1][2][l12-1], v = b[2][1][l21-1];
            l12--, l21--, cnt++;
            ans += to_string(u);
            ans += 'w';
            ans += to_string(v);
            ans += 'i';
        }
        ww = min(l13, l31);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[1][3][l13-1], v = b[3][1][l31-1];
            l13--, l31--, cnt++;
            ans += to_string(u);
            ans += 'w';
            ans += to_string(v);
            ans += 'n';
        }
        ww = min(l32, l23);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[3][2][l32-1], v = b[2][3][l23-1];
            l32--, l23--, cnt++;
            ans += to_string(u);
            ans += 'n';
            ans += to_string(v);
            ans += 'i';
        }
        //分组型模拟
        int res = l23+l31+l12;
        cnt += (res/3)*2, res /= 3;
        int rr = l23;
        while(res--)
        {
            rr--;
            ans += to_string(b[2][3][rr]);
            ans += 'i';
            ans += to_string(b[1][2][rr]);
            ans += 'w';
            ans += to_string(b[2][3][rr]);
            ans += 'w';
            ans += to_string(b[3][1][rr]);
            ans += 'n';
        }
        res = l21+l32+l13;
        cnt += (res/3)*2, res /= 3;
        rr = l21;
        while(res--)
        {
            rr--;
            ans += to_string(b[2][1][rr]);
            ans += 'i';
            ans += to_string(b[3][2][rr]);
            ans += 'n';
            ans += to_string(b[2][1][rr]);
            ans += 'n';
            ans += to_string(b[1][3][rr]);
            ans += 'w';
        }
        printf("%d\n", cnt);
        int wwww = 0;
        for(int i = 0; i < ans.size(); i++) 
        {
            //按输出要求输出
            if((ans[i] == 'w') || (ans[i] == 'i') || (ans[i] == 'n')) cout << " ";
            cout << ans[i];
            if((ans[i] == 'w') || (ans[i] == 'i') || (ans[i] == 'n')) cout << " ", wwww++;
            if(wwww == 2) cout << '\n',  wwww = 0;
        }
    }
    return 0;
}