admin 管理员组

文章数量: 1086019

抽签 （抽四次，和为m否？放回）

题目

       你的朋友提议玩一个游戏：将写有数字的n个纸片放入口袋中，你可以从口袋中抽取4次纸片，每次记下纸片上的数字后都将其放回口袋中。如果这4个数字的和是m，就是你赢，否则就是你的朋友赢。你挑战了好几回，结果一次也没赢过，于是怒而撕破口袋，取出所有纸片，检查自己是否真的有赢的可能性。请你编写一个程序，判断当纸片上所写的数字是k1, k2, …, kn时，是否存在抽取4次和为m的方案。如果存在，输出Yes；否则，输出No。(1<=n<=50, 1<=m<=1e8, 1<=ki<=1e8)

 

样例

输入：

n = 3, m = 10

k = 1, 3, 5

n = 3, m = 9

k = 1, 3, 5

 

输出：

YES

NO

 

题解

1、暴力（n四次）

int flag = 0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)for(int l=0;l<n;l++)if(a[i]+a[j]+a[k]+a[l]==m)flag = 1;if(flag) printf("YES\n");
else printf("NO\n");

2、最后一次二分（n³logn）

二分搜索是否有 m-x[i]-x[j]-x[k]

# include <cstdio>
# include <algorithm>using namespace std;
const int maxn = 1e8 + 10;int n, m;
int x[maxn];int fin(int a)
{int l = 0, r = n;while(r > l){int mid = (l + r) >> 1;if(x[mid] == a) return 1;else if(x[mid] < a) l = mid +1;else r = mid;}return 0;
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&x[i]);sort(x,x+n);int flag = 0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)if(fin(m-x[i]-x[j]-x[k]))flag = 1;if(flag) printf("YES\n");else printf("NO\n");return 0;
}

3、最后两次二分（n²logn）

二分搜索 m-x[i]-x[j]

# include <cstdio>
# include <algorithm>using namespace std;
const int maxn = 10000;
int x[maxn], k[maxn*maxn];
int nu = 0; int fin(int a)
{int l = 0, r = nu;while(r > l){int mid = (l + r) >> 1;if(k[mid]==a) return 1;if(a > k[mid]) l = mid+1;else r = mid;}return 0;
}int main()
{int n, m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&x[i]);for(int i=0;i<n;i++)for(int j=0;j<n;j++)k[nu++] = x[i] + x[j];sort(k,k+nu);int flag = 0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(fin(m-x[i]-x[j]))flag = 1;if(flag) printf("YES\n");else printf("NO\n");return 0;
}

 

本文标签： 抽签 （抽四次，和为m否放回）

版权声明：本文标题：抽签 （抽四次，和为m否？放回） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693761892a241320.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。