1384:珍珠(bead)

简介: 1384:珍珠(bead)

1384:珍珠(bead)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

有n颗形状和大小都一致的珍珠,它们的重量都不相同。n为整数,所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间,即在所有珍珠的重量中,该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法:

给你一架天平用来比较珍珠的重量,我们可以比出两个珍珠哪个更重一些,在作出一系列的比较后,我们可以将某些肯定不具备中间重量的珍珠拿走。

例如,下列给出对5颗珍珠进行四次比较的情况:

1、珍珠2比珍珠1重

2、珍珠4比珍珠3重

3、珍珠5比珍珠1重

4、珍珠4比珍珠2重

根据以上结果,虽然我们不能精确地找出哪个珍珠具有中间重量,但我们可以肯定珍珠1和珍珠4不可能具有中间重量,因为珍珠2、4、5比珍珠1重,而珍珠1、2、3比珍珠4轻,所以我们可以移走这两颗珍珠。

写一个程序统计出共有多少颗珍珠肯定不会是中间重量。

【输入】

第一行包含两个用空格隔开的整数N和M,其中1≤N≤99,且N为奇数,M表示对珍珠进行的比较次数,接下来的M行每行包含两个用空格隔开的整数x和y,表示珍珠x比珍珠y重。

【输出】

一行包含一个整数,表示不可能是中间重量的珍珠的总数。

【输入样例】

5 4

2 1

4 3

5 1

4 2

【输出样例】

2

1. //示例代码 Floyed 暴力求解
2. #include <bits/stdc++.h>
3. using namespace std;
4. int a[105][105];
5. int n,m,x,y,ans,t;
6. int main() {
7.  cin>>n>>m;
8.  for(int i=1;i<=m;i++){
9.    cin>>x>>y;a[x][y]=1;
10.   }
11.   for(int k=1;k<=n;k++)
12.     for(int i=1;i<=n;i++)
13.       for(int j=1;j<=n;j++)
14.         if(a[i][k]==1&&a[k][j]==1) a[i][j]=1;
15.   for(int i=1;i<=n;i++){
16.     t=0;//统计 i>j 的个数
17.     for(int j=1;j<=n;j++) if(a[i][j]==1) t++;
18.     if(t>=(n+1)/2) ans++; //i>j 的个数
19.     t=0;//统计 j>i 的个数
20.     for(int j=1;j<=n;j++) if(a[j][i]==1) t++;
21.     if(t>=(n+1)/2) ans++;
22.   }
23.   cout<<ans;
24. return 0;
25. }
1. //示例代码 深搜求解
2. #include <bits/stdc++.h>
3. using namespace std;
4. bool a1[205][205],a2[205][205],b[205];
5. int n,m,x,y,ans,t;
6. void dfs(int p,bool a[205][205]){
7.  int i; b[p]=1;
8.  for(i=1;i<=n;i++){
9.    if(a[p][i] && !b[i]) dfs(i,a);
10.   }
11.   t++;
12. }
13. int main() {
14.   cin>>n>>m;
15.   for(int i=1;i<=m;i++){
16.     cin>>x>>y;
17.     a1[x][y]=1;//a1  x>y
18.     a2[y][x]=1;//a2  y>x
19.   }
20.   //统计多少个珍珠的重量比(n+1)/2以上个数的珍珠重
21.   for(int i=1;i<=n;i++){
22.     t=0;
23.     memset(b,0,sizeof(b));
24.     dfs(i,a1);
25.     if(t>(n+1)/2)ans++;
26.   }
27.   //统计多少个珍珠的重量比(n+1)/2以上个数的珍珠轻
28.   for(int i=1;i<=n;i++){
29.     t=0;
30.     memset(b,0,sizeof(b));
31.     dfs(i,a2);
32.     if(t>(n+1)/2)ans++;
33.   }
34.   cout<<ans;
35. return 0;
36. }


相关文章
|
存储 算法
【堆】数据结构堆的实现(万字详解)
【堆】数据结构堆的实现(万字详解)
635 0
|
9月前
|
NoSQL Java Redis
Spring Boot 自动配置机制:从原理到自定义
Spring Boot 的自动配置机制通过 `spring.factories` 文件和 `@EnableAutoConfiguration` 注解,根据类路径中的依赖和条件注解自动配置所需的 Bean,大大简化了开发过程。本文深入探讨了自动配置的原理、条件化配置、自定义自动配置以及实际应用案例,帮助开发者更好地理解和利用这一强大特性。
1474 15
|
Java 测试技术 数据库
mybatisPlus在Springboot中的使用
这篇文章详细介绍了如何在Spring Boot项目中集成和使用MyBatis-Plus框架,包括依赖配置、数据库设置、项目结构、实体类定义、启动类配置、Mapper接口编写以及通过单元测试进行的增删改查操作示例。
mybatisPlus在Springboot中的使用
|
存储 运维 Linux
Linux磁盘精准缩容:操作详解与技巧
在Linux系统管理中,有效的磁盘空间优化对于维护系统性能至关重要。本文将深入探讨如何在Linux环境下安全地进行磁盘缩容,帮助你合理调整存储资源,确保系统高效运行。跟随本篇的步骤,一起优化你的Linux系统磁盘空间!
Linux磁盘精准缩容:操作详解与技巧
|
IDE 开发工具 Python
【Python】已解决:pip安装第三方模块(库)与PyCharm中不同步的问题(PyCharm添加本地python解释器)
【Python】已解决:pip安装第三方模块(库)与PyCharm中不同步的问题(PyCharm添加本地python解释器)
2704 0
|
小程序
微信小程序的模态框制作(最详细)
微信小程序的模态框制作(最详细)
|
存储 SQL 关系型数据库
MySQL的参数optimizer_switch
`optimizer_switch`是MySQL系统变量,用于控制查询优化器行为。它由键值对组成,如`index_merge=on/off`,用于开启或关闭特定优化功能。要查看当前设置,运行`SHOW VARIABLES LIKE &#39;optimizer_switch&#39;;`,修改则用`SET`命令,如`SET optimizer_switch=&#39;index_merge=off&#39;;`。
430 1
|
项目管理 智能硬件 测试技术
带你读《天猫精灵:如何在互联网公司做硬件》——天猫精灵发展史
带你读《天猫精灵:如何在互联网公司做硬件》——天猫精灵发展史
带你读《天猫精灵:如何在互联网公司做硬件》——天猫精灵发展史
|
索引
【Qt上位机】打开本地表格文件并获取其中全部数据
本文给出了利用Qt编写一个上位机,实现打开本地表格文件,获取表格总行列数,操作单个单元格以及获取全部单元格内容并输出的解决办法,仅供参考。
480 1
|
JSON 自然语言处理 PHP
MyCms 自媒体系统 v4.1 发布,对接公众号文章排版发布
MyCms 是一款基于 Laravel 开发的开源免费的开源多语言商城 CMS 企业建站系统。
271 24
MyCms 自媒体系统 v4.1 发布,对接公众号文章排版发布