1068. Find More Coins (30)

2019-11-08 02:58:43

字體：大中小

供稿：網(wǎng)友

可能排序太費(fèi)時(shí)間，用map話對(duì)于重復(fù)的直接次數(shù)+1即可，不需要排序

最后個(gè)測(cè)試點(diǎn)超時(shí)的代碼

#include<iostream>#include<vector>#include<algorithm>#PRagma warning(disable:4996)using namespace std;int N, M;vector<int> all;int add = 0;vector<int> path;void traver(int index){ if (add == M) { int flag = 0; for (auto x : path) if (flag == 0) { printf("%d", x);flag = 1; } else printf(" %d", x); printf("/n"); exit(0); } if (add + all[index + 1] > M) return; for (int t = index + 1;t < N;t++) { if (add + all[t] > M) break; path.push_back(all[t]); add += all[t]; traver(t); path.pop_back(); add -= all[t]; }}int main(){ scanf("%d %d", &N, &M); all.resize(N); for (int t = 0;t < N;t++) scanf("%d", &all[t]); sort(all.begin(), all.end()); for (int t = 0;t < N;t++) { if (all[t] > M) break; path.push_back(all[t]); add = all[t]; traver(t); path.pop_back(); } printf("No Solution/n");}

通過(guò)的代碼

#include<iostream>#include<vector>#include<map>#include<algorithm>#pragma warning(disable:4996)using namespace std;int N, M;map<int,int> all;int add = 0;vector<int> path;bool findc(int M){ auto it = all.begin(); while (it!=all.end() && it->first <= M) { if (it->second) { it->second--; if ((*it).first == M) { path.push_back(it->first); return true; } else if (findc(M - it->first)) { path.push_back(it->first); return true; } else { it->second++; } } it++;; } return false;}int main(){ scanf("%d %d", &N, &M); for (int t = 0;t < N;t++) { int temp; scanf("%d", &temp); if (temp <= M) all[temp] += 1; } if(!findc(M)) printf("No Solution/n"); else { int first=1; for (auto it = path.rbegin();it != path.rend();it++) if (first) { printf("%d", *it); first--; } else printf(" %d", *it); cout << endl; }}

上一篇：加載外部資源

下一篇：2017-02-18