POJ 3063 Sherlock Holmes
发布日期:2022-02-05 18:27:28 浏览次数:5 分类:技术文章

本文共 3387 字,大约阅读时间需要 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]
{
double k=min((double)r[0]/(m/2*n),(double)r[1]/(m/2*n));
if(k>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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:TYVJ 1434 黑匣子
下一篇:洛谷 1761 正方形

发表评论

最新留言

逛到本站,mark一下
[***.191.171.24]2022年08月17日 06时53分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

python之logger 2019-12-12 23:02:26
python之爬虫 2019-12-12 23:02:27
Python读取配置文件之python2与python3的区别 2019-12-12 23:02:27
Hive SQL优化 2019-12-12 23:02:26
Python代码审查 2019-12-12 23:02:26
神经网络常见激活函数(包含tensorflow2的api) 2019-12-12 23:02:26
tensorflow2之数据管道Dataset 2019-12-12 23:02:25
tensorflow2之数学运算 2019-12-12 23:02:25
如何构建指标体系--笔记 2019-12-12 23:02:25
LaTeX数学表达式 2019-12-12 23:02:25
tensorflow2之切片 2019-12-12 23:02:25
AirFlow之安装 2019-12-12 23:02:24
实时数据同步 2019-12-12 23:02:24
数据库概况查阅 2019-12-12 23:02:24
hive metastore为MySQL时的中文乱码问题 2019-12-12 23:02:24
白噪音及其检验 2019-12-12 23:02:23
单因子方差分析 2019-12-12 23:02:23
Elasticsearch笔记 2019-12-12 23:02:22
DW及建模 2019-12-12 23:02:23
非参数检验 2019-12-12 23:02:22