試題 演算法訓練 娜神平衡
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
娜娜是一個特別可愛的女孩子，作為學神的她最近在情感方面出現了一點點小問題，
她暗戀的琦琦是一名學霸，他只喜歡長得漂亮和學習很好的女生，
娜娜學習確實很神，但是她在琦琦面前卻總是表現不出平時的神力，
琦琦感受到了娜娜對他的愛，但是他還是覺得娜娜的學習并不是特別好，于是他出了一道題給娜娜，
“娜娜，我們之間的關系需要在不斷深入的同時保持一定的平衡，不可以你總是強勢或者我總是弱勢，”
琦琦給了娜娜一些兩兩不等的數，希望娜娜能把這些數分成兩組A和B，滿足以下條件：
1：每一次只能操作一個數，即只取出一個數分入A中或B中；
2：每一次操作完成后，A中數之和與B中數之和的差不能超過r，
新時代的丘位元們啊，幫幫娜娜吧！(笑)
輸入格式
輸入共兩行，
第一行包括兩個正整數n和r，n表示琦琦一共給了n個數，r的意義見題目描述，
第二行包括n個正整數，分別表示琦琦給的n個數，
輸出格式
輸出共兩行，分別把A與B兩組數按從小到大輸出，
注意輸入中n個數的第一個必須分入A組，
琦琦保證這樣的輸出唯一，
樣例輸入
4 10
9 6 4 20
樣例輸出
4 6 9
20
樣例說明
先把4和6先后分入A組，再把20分入B組，最后把9分入A組，
資料規模和約定
很小，真的很小，(題目沒明寫，我查資料集只有: 1 <= n <= 10)
簡單粗暴的思路：
- 排列后，按順序將數優先放入A中，放進，記錄
- A中放不進，放B中，放進，記錄
- B中放不進，資料放回隊尾，下次再列舉
- 按照記錄的順序回溯，將最后一次放入陣列中的元素洗掉，放回隊尾，下次再列舉
- 回圈直到佇列沒有元素列舉
要點：
- 排序資料，便于列舉判斷
- 使用佇列存盤資料，列舉失敗的資料可以放回隊尾，下次再列舉
- 使用堆疊存盤列舉成功的順序，便于回溯(正因為把順序保存了下來，免于用遞回)
- 題目要求第一個數只能放在A中，因此，只要發現B中存在第一個數，就把B當成A就行了(由答案的唯一性，可以知道一個組中的數永遠待在一起，因此只要把存有第一個數的組當成A就可以了，沒必要糾結于優先列舉進哪個陣列)
代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int q[N], first;
vector<int> a, b, pre;
int n, m, sa, sb;
int main(){
scanf("%d%d", &n, &m);
for (int i = 0 ;i < n; i ++) scanf("%d", &q[i]);
first = q[0]; //保存第一個數，根據題意是一定要存進A里的
sort(q, q + n); //排序，從小到大地列舉，關鍵
int hh = 0, tt = n - 1; //模擬佇列
while (hh <= tt){ //佇列為空，列舉完成
int t = q[hh ++];
sa += t;
a.push_back(t); //列舉的順序是優先把小的數放進A
pre.push_back(1); //存盤已經成功列舉的順序， 1表示存進了A，2表示存進了B
if (abs(sa - sb) > m){
sa -= t;
a.pop_back(); //超過限制，選不了
pre.pop_back();
sb += t;
b.push_back(t); //存進B
pre.push_back(2);
if (abs(sa - sb) > m){
sb -= t;
b.pop_back(); //超過限制，選不了
pre.pop_back();
q[++ tt] = t; //目前，兩組都無法放這個數，將這個數存回佇列，下次再列舉
if (pre.back() == 1) q[++ tt] = a.back(), a.pop_back(), pre.pop_back(); //之前某個數放錯了，撤銷式地回溯，放入佇列，下次再列舉
else q[++ tt] = b.back(), b.pop_back(), pre.pop_back();
}
}
}
sort(a.begin(), a.end()); //排序答案，題目要求
sort(b.begin(), b.end());
for (int i = 0 ; i < b.size(); i ++) //若題目要求的第一個數在B中，則替換AB陣列，保證第一個數在A中
if (b[i] == first){
swap(a, b);
break;
}
for (int i = 0 ; i < a.size(); i ++) printf("%d ", a[i]);
puts("");
for (int i = 0 ; i < b.size(); i ++) printf("%d ", b[i]);
return 0;
}
吐槽：
這題應該不算難(畢竟我都會)，看到其他人有用狀態壓縮和dfs的，我發現我的思路挺簡單粗暴的，就想分享一下，
嗷，80分沒過最后一個資料的，不是因為題目有問題，而是題意要求第一個資料必須在A中，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423818.html
標籤：其他
下一篇：大前端演算法篇之二叉樹遍歷