问题描述：
将写有数字的 n个纸片放入口袋中，你可以从口袋中抽取 4次纸片，每次记下纸片上的数字后都将其放回口袋中。如果这 4个数字的和是 m，就是你赢，否则就是你的朋友赢。你挑战了好几回，结果一次也没赢过，于是怒而撕破口袋，取出所有纸片，检查自己是否真的有赢的可能性。请你编写一个程序，判断当纸片上所写的数字是 k 1 ,k 2 , …, k n 时，是否存在抽取 4次和为 m的方案。如果存在，输出 Yes；否则，输出 No。
限制条件
1 ≤ n ≤ 50
1 ≤ m ≤ 108
1 ≤ k i ≤108
输入：
n = 3 m = 10 k = {1, 3, 5}
输出：
YES（1 + 1 + 3 + 5 = 10）
解题思路：
由于问题规模小，可以直接四重循环
1 #include<bits/stdc++.h> 2 #define FOR(i, a, b) for(int i = a; i < b; i++) 3 using namespace std; 4 int main() 5 { 6 int n, m, k[55]; 7 cin >> n >> m; 8 for(int i = 0; i < n; i++)cin >> k[i]; 9 bool ans = false; //标记是否找到解 10 FOR(i, 0, n)FOR(j, 0, n)FOR(r, 0, n)FOR(s, 0, n) 11 { 12 if(k[i] + k[j] + k[r] + k[s] == m)ans = true; 13 } 14 if(ans)cout<<"YES"<<endl; 15 else cout<<"NO"<<endl; 16 }
拓展：
如果问题规模扩大，n属于1到1000，上述算法肯定失效。所以必须优化算法：
最开始我们考虑的是检查是否有ki,kj,kr,ks之和等于m，算法时间复杂度为O(n4)。转移表达式，检查是否存在ks = m - ki - kj - kr;可以想到，枚举外面三层，最后判断ks是否存在即可，判断的话可以用二分查找，这样时间复杂度降低成了O(n3log(n))。但是对于1000的数据还是需要很长的时间，所以考虑是否存在kr+ks = m - ki - kj。这种情况不能直接使用二分搜索，但是，如果事先枚举出所有的kr + ks之和，并排序，就可以进行二分搜索。这样预处理+排序+二重循环搜索时间复杂度降低成了O(n2log(n))。这样n = 1000也可以轻易地过了。
1 #include<bits/stdc++.h> 2 #define FOR(i, a, b) for(int i = a; i < b; i++) 3 using namespace std; 4 const int maxn = 1e3 + 10; 5 int k[maxn]; 6 int kk[maxn * maxn]; 7 int tot; 8 int n, m; 9 bool binary_search(int x) 10 { 11 int l = 0, r = tot; 12 while(l <= r) 13 { 14 int m = (l + r) / 2; 15 if(kk[m] == x)return true; 16 if(kk [m] < x)l = m + 1; 17 else r = m - 1; 18 } 19 return false; 20 } 21 void init()//可以直接用STL里面的set，把两层循环枚举的和放入set中，直接判断是否存在（set中的count函数） 22 { 23 for(int i = 0; i < n; i++) 24 { 25 for(int j = i; j < n; j++)kk[tot++] = k[i] + k[j]; 26 } 27 sort(kk, kk + tot);//排序 28 } 29 int main() 30 { 31 cin >> n >> m; 32 for(int i = 0; i < n; i++)cin >> k[i]; 33 init(); 34 bool ans = false; //标记是否找到解 35 FOR(i, 0, n)FOR(j, 0, n) 36 { 37 if(binary_search(m - k[i] - k[j]))ans = true; 38 } 39 if(ans)cout<<"YES"<<endl; 40 else cout<<"NO"<<endl; 41 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
