PAT_甲級_1113 Integer Set Partition (25分) (C++)【簽到題】

目錄

​​1，題目描述​​

​​題目大意​​

​​2，思路​​

​​3，AC代碼​​

​​4，解題過程​​

​​第一搏​​

​​第二搏​​

​​第三搏​​

1，題目描述

• disjoint：（使） 脫節，（使）解體，（使）脫臼；

Sample Input 1:

10
23 8 10 99 46 2333 46 1 666 555      

Sample Output 1:

0 3611      

Sample Input 2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85      

Sample Output 2:

1 9359      

題目大意

将一個數組分成兩個小數組（注意是數組，不是集合），這兩個小數組滿足：規模之差最小，各數組的和sumA，sumB之差的絕對值最大。

2，思路

直接上代碼吧。。。

3，AC代碼

#include<bits/stdc++.h>
using namespace std;

int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N, n, num = 0, sum = 0, sumA = 0;
    cin>>N;
    vector<int> data;
    for(int i = 0; i < N; i++){
        cin>>n;
        data.push_back(n);
        sum += n;
    }
    sort(data.begin(), data.end());
    for(int i = 0; i < N / 2; i++){
        sumA += data[i];
    }
    cout<<N%2<<' '<<sum-sumA-sumA;
    return 0;
}      

4，解題過程

第一搏

這25分嗎？？？

我劈裡啪啦一頓操作就敲出了代碼

#include<bits/stdc++.h>
using namespace std;

int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N, n, sumB = 0, sumA = 0;
    cin>>N;
    set<int> data;
    for(int i = 0; i < N; i++){
        cin>>n;
        data.insert(n);
        //sum += n;
    }
    int index = 0;
    //cout<<data.size()<<endl;
    for(auto it : data){
        if(index < data.size() / 2){
            sumA += it;
            index++;
        }else
            sumB += it;

    }
    cout<<sumA <<' '<<sumB<<endl;
    cout<<N%2<<' '<<sumB-sumA;
    return 0;
}      

但是得出的結果。。。

第二搏

冷靜分析之後，發現，原始序列中有重複元素46，3657-46=3611，于是我懷疑可能并不是将所有元素去重然後對半分成兩部分，而是将重複的元素放入另一個集合，使元素在各自的小set裡是獨一無二的。

于是我這樣：

#include<bits/stdc++.h>
using namespace std;

int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N, n, num = 0, sum = 0, sumA = 0;
    cin>>N;
    map<int, int> data;
    for(int i = 0; i < N; i++){
        cin>>n;
        if(data[n] < 2){
            data[n]++;
            sum += n;
            num++;
        }
    }
    int index = 0;
    //cout<<data.size()<<endl;
    for(auto it : data){
        if(index < num / 2){
            sumA += it.first;
            index++;
        }else
            break;

    }
    //cout<<sumA <<' '<<sumB<<endl;
    cout<<num%2<<' '<<sum-sumA-sumA;
    return 0;
}      

第三搏

水這麼深嗎？？？

上網查閱之後，這題沒那麼複雜呀。。。

我又重新試了一下。

沒毛病。。。

瓦特了瓦特了瓦特了