首页 > 代码库 > 1959 拔河比赛
1959 拔河比赛
1959 拔河比赛
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。
输入描述 Input Description
数据的第1行是一个n，表示参加拔河比赛的总人数，n<=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1<=weight<=450）。
输出描述 Output Description
包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。
样例输入 Sample Input
3
100
90
200
样例输出 Sample Output
190 200
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
动态规划
题解：
无脑的置随机数，取小
AC代码：
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<ctime>using namespace std;int n,s,a[110];int main(){ srand(time(0)); cin>>n; for(int i=1;i<=n;i++) cin>>a[i],s+=a[i]; int ans=9999999; for(int k=1;k<=100000;k++){ for(int i=1;i<=n;i++){ int x=rand()%n+1; int y=rand()%n+1; swap(a[x],a[y]); } int t=0; for(int i=1;i<=n/2;i++) t+=a[i]; int tans=abs(s-t-t); if(ans>tans) ans=tans; } printf("%d %d\n",(s-ans)/2,(s+ans)/2); return 0;}
1959 拔河比赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。