Codeforces 1474C - Array Destruction (設計解題、數學推理)

題目大意

有一個陣列，裡面只有正整數，要進行以下操作：

• 一開始先選出某一數字為 \(x\)
• 移除陣列中的兩個元素，定義 \(a,b\)，移除時必須符合此公式 \(a+b=x\)
• 之後必須將 \(max(a,b) = x \)，讓 a or b 中的最大值成為 x

如果可以透過規則讓陣列元素全部被清空就輸出 “Yes”，否則就輸出 “NO”

舉例： \(a = [3,5,1,2] \)，那清空的操作如下

• \(x=6=5+1\)
• \(x=5=2+3\)

題目連結

重點觀念

• 對於數字的邏輯推理
• 快速找出題目的重點與其作答方向

分析

好題，這種給你一種遊戲方式來讓你去解出來的，我稱之為「設計解題」，這種題目由於沒辦法先前準備，因此很吃反應能力跟思考速度，一個不小心可能就亂掉了QQ。

QUESTION A: 如果找出 \(x\)？

首先，\(x\) 值一定要是比陣列中所有元素更大，且要讓陣列元素中的某兩個值相加 \(a,b\)。
再來，\(x\) 值會變成\(a,b\)中取最大的值做為下一次的 \(x\)。

因此我們可以知道，\(x\) 一定會遞減。

QUESTION B: 那 \(x\) 值一開始會是多少呢？有辦法推出來嘛？

沒有辦法。
因為我們不確定哪兩個元素為 \(x\) 之後，就可以讓後面不斷運行的操作都可以成立，每次都可以順利讓 \(a+b=x\)。

因此，在這種情況下只剩下暴力嘗試去找出其一開始的 \(x\) 值，讓元素中最大的數字去加上元素中其中另一元素當作 x，不斷反覆去嘗試配對，直到可以將所有數字用完就是正解。

至於為甚麼是先讓元素中最大的數字去配陣列中其他元素？
我們可以舉個例子： \(a = [3,5,1,2] \)

• 一開始我們使用 \(a+b=x\) 等同於 \(3+1=4\)，這樣就不是讓元素中最大的數字去配陣列中其他元素
• 再來我們必須使用 3 來讓成為下次的 \(x\)，此時我們可以發現 5 這個元素再也沒有辦法被移除，因為 x 已經小於 5 了，因此這種配對方式一定會失敗。
• 這點我們有在 QUESTION A 討論過，這裡透過舉例讓讀者更加清晰。

參考來源

Codeforces Round #696 Editorial

心得

原本我在寫這題時一直卡關，想不出來怎麼解…，數字推理與反應速度慢的不可思議啊QQQQ，之後透過不斷的寫演算法題目來讓我的思考能力變快、更迅速，一定可以幫忙到生活上的所有事物，可能我會不清楚在哪裡用到，但現在的我認為這一定是會讓自己變更聰明的學習！

雖然學的過程中真的蠻痛苦的…，希望我可以多努力加油。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1000020
using namespace std;
int t, n, x, num[MAXN], a[MAXN];  
// a 為題目給的元素陣列 
//num 為那個數字有幾個，舉例： num[2]=1 a陣列中有 2 這個數值並且有一個
vector<pair<int,int> > record; //紀錄要輸出的 pair

void solve(){
    sort(a,a+2*n); //先進行排序，方便找出陣列中最大的數值
    for(int i = 0; i < 2*n-1; i++){ //陣列中最大的數值與某一數值合併
        record.clear(); //清空紀錄
        memset(num, 0, sizeof(num)); //先將 num 清空
        for(int j = 0; j <= 2*n-1; j++) //讓 num 的資料與 a 同步
            num[a[j]]++;
        x = a[i] + a[2*n-1]; //最一開始的 x
        //cout << "x is " << x << '\n';
        int cnt = n; //需要組成幾個 pair，如果都可以成功組出表示沒問題
        while(cnt){ //這裡的判斷是剩下幾個 pair
            int pos = 2*n-1; //從最大開始找， 2*n-1 為初始陣列中最長的位置
            while(pos > 0 && num[a[pos]] == 0) 
            //從後面開始算，如果後面那些值被用過就往前算，用來找出當前最大的 x
                pos--;
            num[a[pos]]--; num[x-a[pos]]--; //更新 num 值狀態，那兩個值透過規則被提出
            //x=a+b，當 a,x 值固定 則 b(x-a[pos]) 值一定是固定
            // 注意，這裡的 a 不是陣列 a，是我們定義的數值 a
            if(num[a[pos]] < 0 || num[x-a[pos]] < 0) 
            //如果 num 值裡面是 -1 就表示陣列中沒有這個數字，不能拿來當成一個 pair
                break; //再換新組合
            record.push_back({a[pos], x-a[pos]}); 
            //記錄這個 pair，因為通過上面的 if 表示通過考驗
            //cout << a[pos] << ' ' << x-a[pos] << '\n';
            x = max(a[pos], x-a[pos]); //選擇下一個 x
            cnt--; //還需要的 pair 數量 -1
        }
        if(cnt == 0 ){ //等於 0 表示，已經可以完全匹配到了
            cout << "YES\n";
            cout << record[0].first + record[0].second << '\n'; 
            //題目要求輸出最一開始的 x
            for(auto it: record) //輸出所有配對
                cout << it.first << ' ' << it.second << '\n' ;
            return; //由於配對成功，所以 return
        }
    }
    cout << "NO\n"; //配對失敗
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < 2*n; i++) //輸入資料
            cin >> a[i];
        solve();
    }
    return 0;
}