88.错账 (15分)
C时间限制:3 毫秒 | C内存限制:3000 Kb
题目内容:
某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某1笔或几笔。如果已知明细账目清单,能通过编程找到漏掉的是
哪1笔或几笔吗?
如果有多种可能,则输出所有可能的情况。
输入描述
第一行是有错的总金额,接下来是一个整数n,表示下面将要输入的明细账目的条数。
再接下来是n行整数,分别表示每笔账目的金额。为了方便,这里假设所有的金额都是整数;每笔金额不超过1000,金额的明细条
数不超过100。
输出描述
所有可能漏掉的金额组合。每个组合1行。组合之间,按首数据在输入中的次序决定组合的先后,如果首数据是同一个,则看下一
个数据的位置。每组金额内部的几个数据按照值从小到大排列,中间用空格分开。
输入样例
6
5
3
2
4
3
1
输出样例
3 4
1 3 3
1 2 4
思路:直接dfs,按顺序搜索,搜到的结果排序, 同时用set判重,注意每行输入末尾不能有空格。
set使用vector的例子:
#include <iostream> #include <set> #include <vector> using namespace std; int main(){ set<vector<int> > myset; vector<int> a; a.push_back(2); myset.insert(a); vector<int> b; b.push_back(2); myset.insert(b); cout << myset.size() <<endl; // cout << myset.find(b) << endl; vector<int> c; cout << myset.count(c) <<endl; return 0; }
本题代码:
#include <iostream> #include <algorithm> #include <set> #include <vector> using namespace std; int mon[105]; int lou, k; set<vector<int> > myset; void dfs(int x, int sum, int tep[], int ct){ if(x > k){ return ; } if(sum == lou){ sort(tep, tep + ct); vector<int> aa; for(int i = 0; i < ct; i++){ aa.push_back(tep[i]); // cout << tep[i] << " "; } if(myset.count(aa) == 0){ myset.insert(aa); cout << tep[0]; for(int i = 1; i < ct; i++){ cout << " " << tep[i] ; } cout << endl; } return ; } tep[ct] = mon[x]; dfs(x + 1, sum + mon[x], tep, ct + 1); dfs(x + 1, sum, tep, ct); } int main(){ int tep[105]; cin >> lou >> k; int sum = 0; for(int i = 0; i < k; i++){ cin >> mon[i]; sum += mon[i]; } lou = sum - lou; dfs(0, 0, tep, 0); return 0; }