紫薯P50 例题3-4

一、题意

输入有好几组。
每组第一行一个数n，第二行开始，每行n个数，数字范围为1-9。
每组第二行为一个参照序列ans。
对于之后的每个序列行，它与ans序列相比，有A个数字位置正确，有B个数字在两个序列中都出现过但位置不对。输入(A, B)。
当有一行全为0时，该组结束；当n为0时，输入结束。

二、解析

统计每个数字在ans序列中出现的次数cnt_a[10]；对于之后与之对比的序列b，统计每个数字在b序列中出现的次数cnt_b[10]；统计每个数字在两个序列中位置相同的次数cnt_same[10]。
则 A 为所有数字位置正确的次数之和；B比较难想，就是每个数字在两个序列中出现次数的较小值减去位置相同的次数。（B可以用一个二分图来理解）

三、代码

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 1000 + 5;
int n, kase = 1;

int main() {
    while(cin >> n && n) {
        cout << "Game " << kase ++ << ":\n";
        int ans[maxn], cnt_a[10], cnt_b[10], cnt_same[10];
        fill(cnt_a, cnt_a + 10, 0);
        for(int i = 0; i < n; i ++) {
            cin >> ans[i];
            cnt_a[ans[i]] ++;
        }

        while(1) {
            fill(cnt_b, cnt_b + 10, 0);
            fill(cnt_same, cnt_same + 10, 0);
            bool ok = 0;
            for(int i = 0, x; i < n; i ++) {
                cin >> x;
                cnt_b[x] ++;
                if(x == ans[i]) cnt_same[x] ++;
                if(x != 0) ok = 1;
            }
            if(!ok) break;

            int A = 0, B = 0;
            for(int i = 1; i < 10; i ++) A += cnt_same[i], B += min(cnt_a[i], cnt_b[i]) - cnt_same[i];
            cout << "    (" << A << "," << B << ")" << endl;
        }
    }
}

四、归纳

  • 注意局部变量、数组的初始化
  • 遇到数学题要先思考清楚，不要拿到题目就敲代码
  • 计数的思想貌似经常用到，可以留意一下

慢慢来总会进步的吧