【题目描述】
有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重。
【输出】
一行包含一个整数,表示不可能是中间重量的珍珠的总数。
【样例输入】
【样例输出】
2
看完题目没思路?其实超简单
弗洛伊德轻松搞定!!!
其实如果有(n+1)/2个珍珠比一个珍珠重,那么这个珍珠一定不在中间。
AC代码如下
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define N 1001
using namespace std;
int heavy[N][N], light[N][N];
int n, m, ans=;
int main()
{
cin>>n>>m;
int a, b;
for (int i=; i<=m; i++){
cin>>a>>b;
heavy[a][b]=;
light[b][a]=;
}
for (int k=; k<=n; k++)
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
if(i!=j && i!=k && j!=k){
heavy[i][j]=heavy[i][j] || (heavy[i][k] && heavy[k][j]); //如果i比k重且k比j重,那么i比j重
light[i][j]=light[i][j] || (light[i][k] && light[k][j]);
}
for (int i=; i<=n; i++){
a=;b=;
for(int j=; j<=n; j++){
if(heavy[i][j])
a++;
else if(light[i][j])
b++;
}
if(a>=(n+)/ || b>=(n+)/) ans++;
}
cout<<ans<<endl;
return ;
}
【Floyd】珍珠的更多相关文章
-
珍珠 Median Weight Bead 977
描述 There are N beads which of the same shape and size, but with different weights. N is an odd numbe ...
-
珍珠(bead)
题目描述 有n颗形状和大小都一致的珍珠,它们的重量都不相同.n为整数,所有的珍珠从1到n编号.你的任务是发现哪颗珍珠的重量刚好处于正中间,即在所有珍珠的重量中,该珍珠的重量列(n+1)/2位.下面给出 ...
-
floyd算法学习笔记
算法思路 路径矩阵 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1):又 ...
-
最短路(Floyd)
关于最短的先记下了 Floyd算法: 1.比较精简准确的关于Floyd思想的表达:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B.所以,我们假设maz ...
-
最短路径之Floyd算法
Floyd算法又称弗洛伊德算法,也叫做Floyd's algorithm,Roy–Warshall algorithm,Roy–Floyd algorithm, WFI algorithm. Floy ...
-
UVALive 4431 Fruit Weights --floyd,差分约束?
题意: 给出一些关系用aX <= bY表示, 最后查询aX 和 bY的关系,是>=,==,<=,还是不能确定,还是出现了矛盾. 解法:对每一个关系其实都可以建一条X->Y的边, ...
-
洛谷P1119 灾后重建[Floyd]
题目背景 B地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响.但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车.换句话说,只有连接着两个重建完成的村庄的公路才能 ...
-
UVA10048 Audiophobia[Floyd变形]
UVA - 10048 Audiophobia Consider yourself lucky! Consider yourself lucky to be still breathing and h ...
-
最短路径—Dijkstra算法和Floyd算法
原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html 最后边附有我根据文中Dijkstra算法的描述使用jav ...
随机推荐
-
JAVA多线程 问题 转载
参考:http://ifeve.com/java-multi-threading-concurrency-interview-questions-with-answers/ http://www.cn ...
-
linux-11 基本命令之 -工作期目录切换命令-pwd,cd,
pwd 命令用于显示当前的工作目录,格式为:pwd[选项] @1.查看当前的工作路径: [root@localhost /]# pwd cd 命令用于切换工作路径 格式为:"cd 目录名称& ...
-
测试LVS+Keepalived高可用负载均衡集群
测试LVS+Keepalived高可用负载均衡集群 1. 启动LVS高可用集群服务 此时查看Keepalived服务的系统日志信息如下: [root@localhost ~]# tail -f /va ...
-
JEECMS v8 发布,java 开源 CMS 系统
JEECMSv8 是国内java开源CMS行业知名度最高.用户量最大的站群管理系统,支持栏目模型.内容模型交叉自定义.以及具备支付和财务结算的内容电商为一体: 对于不懂技术的用户来说,只要通过后台的 ...
-
Android开发环境搭建(2015年8月更新)
1. 下载和安装Android SDK Android的官方站点是http://www.android.com: 登录https://developer.android.com/intl/zh-cn ...
-
newlisp 注释生成文档
最近写了一个newlisp_armory库,用来实现一些newlisp自身不支持的操作.比如跨windows和ubuntu的目录拷贝功能等. 自己用的时候,发现没有API reference文档参考, ...
-
CSS盒子的浮动
web前端学习笔记(CSS盒子的浮动) 在标准流中,一个块级元素在水平方向会自动伸展,直到包含它的元素的边界:而在竖直方向和兄弟元素依次排列,不能并排.使用“浮动”方式后,块级元素的表现就会有所不同. ...
-
手把手教小白如何用css+js实现页面中图片放大展示效果
1.前言 很多童鞋会在项目中遇到一些上传图片,展示图片的操作,但是图片呢有大有小,为了页面的美观,有时候我们需要将图片展示成固定宽高度,但是呢,领导就会说,我想看大图片,怎么办?想看就看呀, ...
-
SecureCRT窗口输出代码关键字高亮设置
设置方法: 下载配置文件:本站下载:Highlights.css (下载重命名为 Highlights.ini ) 原站下载:http://download.feralpacket.org/La ...
-
vee-validate表单验证组件
vee-validate是VUE的基于模板的验证框架,允许您验证输入并显示错误 安装 npm i vee-validate --save 引入 import Vue from 'vue'; impor ...