POJ 3063 Sherlock Holmes
发布日期:2022-02-05 18:27:28
浏览次数:18
分类:技术文章
本文共 3318 字,大约阅读时间需要 11 分钟。
Sherlock Holmes
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 662 | Accepted: 213 |
Description
Sherlock Holmes, the well known detective, must solve a puzzling situation. He has n boxes B1, B2, .., Bn , where n is even, each containing m balls. The balls are white and black. Let Bi = (Wi, Bi) denote a box with Wi white balls and Bi black balls. He must partition the boxes into two sets, each consisting of n/2 boxes, such that either the white balls or the black balls hold amajority in both sets. If there is such a majority, let m1 and m2 denote the percentage of the majority balls in each set. Holmes must find very quickly the maximum possible value of min(m1, m2). Can you help Holmes?
Input
There are several testcases. Each data set in the file stands for a particular set of boxes. A data set starts with the number n (n < 10000) of boxes. Follows the number m (m < 10000) of balls, and for each box the number (< 10000) of white and black balls in this specific order. White spaces can occur freely in the input. The input data are correct and terminate with an end of file.
Output
For each set of data the program prints the result to the standard output from the beginning of a line. The program prints the color (W or B) of the balls that hold the majority followed by the maximum value - if there is such a majority, or "No solution" (without quotes) if no majority can be obtained. An input/output sample is in the table below. There is a single data set that contains 4 boxes each containing 30 balls. The first box, for example, contains 17 white balls and 13 black balls. There is only one possible partition of the boxes (B1, B4), (B2, B3), the white balls holding majority. The result for the data set is the identifier W and the maximum value.
Sample Input
43017 1312 1820 1014 16
Sample Output
W 51.67
Source
Southeastern Europe 2006
一开始给的中文题目 居然没有说平均分成两组。。。
只能rand()%2分组+卡时 Wa了3个点
后来平均分后 随机交换两组中的两个+卡次数
写得挺丑的。。。
#include#include #include #include #include #include using namespace std;struct self{int x,y,side;}s[10001];int m,n,a,b,c;double ans,z;int side=-1;int baizong,heizong,num;int l[2],r[2];int x,y;void tongji(){ if(l[0]>r[0]&&l[1]>r[1]) { double k=min((double)l[0]/(m/2*n),(double)l[1]/(m/2*n)); if(k>ans) { ans=k; side=0; } } if(l[0] ans) { ans=k; side=1; } }}void exchange(int x,int y){ l[0]-=s[x].x; r[0]-=s[x].y; l[1]+=s[x].x; r[1]+=s[x].y; s[x].side=1; l[1]-=s[y].x; r[1]-=s[y].y; l[0]+=s[y].x; r[0]+=s[y].y; s[y].side=0; }int main(){ srand(time(NULL)); while(scanf("%d",&m)==1) { scanf("%d",&n); num=0; ans=0; baizong=0; heizong=0; side=-1; l[0]=r[0]=l[1]=r[1]=0; for(a=1;a<=m;a++) { scanf("%d%d",&s[a].x,&s[a].y); baizong+=s[a].x; heizong+=s[a].y; } if(baizong>heizong)side=0; else side=1; for(a=1;a<=m/2;a++) { s[a].side=0; l[0]+=s[a].x; r[0]+=s[a].y; } for(a=m/2+1;a<=m;a++) { s[a].side=1; l[1]+=s[a].x; r[1]+=s[a].y; } while(num<=50000) { num++; x=rand()%m+1; while(s[x].side!=0)x=rand()%m+1; y=rand()%m+1; while(s[y].side!=1)y=rand()%m+1; z=ans; exchange(x,y); tongji(); if(ans>z)if(rand()%1000+1<=50)exchange(y,x);else; else if(rand()%1000+1>=50)exchange(y,x); } if(ans==0) cout<<"No solution"<<'\n'; else if(side==0) cout<<"W "; else cout<<"B "; if(ans!=0)cout< < < <<'\n'; } return 0;}
转载地址:https://blog.csdn.net/li412302070/article/details/13005123 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月06日 12时50分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
LeetCode题解(1384):按年度列出销售总额(SQL)
2019-04-26
LeetCode题解(1393):股票的资本损益(SQL)
2019-04-26
LeetCode题解(1398):购买了产品A和产品B却没有购买产品C的顾客(SQL)
2019-04-26
LeetCode题解(1407):排名靠前的旅行者(SQL)
2019-04-26
LeetCode题解(1412):查找成绩处于中游的学生(SQL)
2019-04-26
LeetCode题解(1421):净现值查询(SQL)
2019-04-26
LeetCode题解(1435):制作会话柱状图(SQL)
2019-04-26
LeetCode题解(1440):计算布尔表达式的值(SQL)
2019-04-26
文件服务器实现基本条件!
2019-04-26
文件服务器-活动目录的讨论
2019-04-26
文件服务器-活动目录的安装
2019-04-26
文件服务器-OU的概念!
2019-04-26
XP HOME 版本的 限制!
2019-04-26
VISTA版本!
2019-04-26
VMware GSX3.2 安装WINDOWS 2008!(1)
2019-04-26
VMware GSX3.2 安装WINDOWS 2008!(2)
2019-04-26
OE问题解决一例!
2019-04-26
利用LDIFDE,CSVDE 批量导出用户!
2019-04-26
ArcServer 无法正常启动,卸载IE7.0!
2019-04-26
为我加油吧-CTO 冲!
2019-04-26