c134 - 00668 - Parliament
題目描述
題目要求找出對於給定的議員數量 N，將議員分成不同人數的委員會，使得委員會的數量最大，且每天協調會的組成都不同。委員會人數必須互不相同。
解題思路
題目觀察發現，對於給定的 N，委員會的人數分配存在一個規律。程式碼中預先計算了從 1 到 1000 的 N 对应的最佳委員會分配方案，並將其儲存在 map 中。對於輸入的 N，直接從 map 中取出對應的委員會分配方案並輸出。這個規律是從 2, 3 開始，每次增加委員會數量，並保持委員會人數互不相同。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n,p=5,k=4,t,st;
vector <int> a={0,9999};
map <int,vector <int>> mp;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<=1000;++i){
if(i<=4){
++a[0];
}
else if(i==p){
a.clear();
for(int j=2;j<k;++j){
a.push_back(j);
}
a.push_back(9999);
p+=k;
++k;
}
else{
for(int j=0;j<a.size();++j){
if(a[j]+1!=a[j+1]){
++a[j];
break;
}
}
}
mp[i]=a;
}
cin >> t;
while(t--){
if(st)cout << "\n";
st=1;
cin >> n;
for(int i=0;i<mp[n].size()-1;++i){
if(i)cout << " ";
cout << mp[n][i];
}
cout << "\n";
}
}