- 浏览: 37646 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
USACO - 2.3.5 - Controlling Companies
原创文章转载请注明出处
摘要:BFS , 模拟
一. 题目翻译
1. 描述:
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下三个条件之一,公司A就可以控制公司B了:
1. 公司A = 公司B。
2.公司A拥有大于50%的公司B的股票。
3.公司A控制K(K >= 1)个公司,记为C1, ..., CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ .... + xK > 50%。
给你一个表,每行包括三个数(i,j,p);表明公司i享有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。至多有100个公司。
写一个程序读入N组数(i,j,p),i,j和p是都在范围(1..100)的正整数,并且找出所有的数对(h,s),使得公司h控制公司s。
2. 格式:
INPUT FORMAT:
第一行: N,表明接下来三对数的数量。{即(i,j,p)的数量}
第二行到第N+1行: 每行三个整数作为一个三对数(i,j,p),如上文所述。{表示i公司拥有j公司 p%的股份}
OUTPUT FORMAT:
输出零个或更多个的控制其他公司的公司。每行包括两个整数A、B,表示A公司控制了B公司。将输出的数对以升序排列。
请不要输出控制自己的公司。
SAMPLE INPUT:
3
1 2 80
2 3 80
3 1 20
SAMPLE OUTPUT:
1 2
1 3
2 3
1. 题意理解(将问题分析清楚,大致用什么思路):
这道题目解法如下, 首先扫描输入, 记录所有公司之间的控制情况。然后遍历每一个公司 (eg:A公司),将该公司直接控制的公司加入链表(eg:B1、B2、B3公司)。然后BFS链表中的所有控制的公司,更新A公司对其他公司的控股(参考条件3),如果大于50%则加入链表中,直到链表中再没有元素。
2. 具体实现(具体实现过程中出现的问题):
我们使用数组control[i][j]表示i公司控制j公司 ,stocks[i][j]表示i公司对j公司控股数量。
具体请参考代码注释。
3. 启示:
注意没有更改的代码出现了integer越界情况
三. 代码
/* ID:fightin1 LANG:JAVA TASK:concom */ package session_2_3_5; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; import java.util.LinkedList; import java.util.Scanner; public class concom { public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); // Scanner in = new Scanner(new BufferedReader(new FileReader( // "concom.in"))); // PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter( // "concom.out"))); int n = in.nextInt(); int[][] stocks = new int[101][101]; //表示i公司对j公司的控股数量 boolean[][] control = new boolean[101][101];//表示i公司控制j公司 for (int i=1;i<=n;i++){ int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); if (c>50){ control[a][b] = true; } stocks[a][b] = c; } for (int i=1;i<=100;i++){ LinkedList<Integer> ll = new LinkedList<Integer>();//用LinkedList记录当前i公司控制的所有公司,用于BFS for (int j=1;j<=100;j++){ if (control[i][j]){ ll.add(j); } } while (ll.size()!=0){ int temp = ll.removeFirst(); for (int j=1;j<=100;j++){ if (!control[i][j]) { stocks[i][j]+=stocks[temp][j];//当前公司控制着temp公司,那么用temp公司控制公司的股份更新当前公司的股份 if (stocks[i][j]>50){//如果大于百分之50,则当前i公司控制j公司,并加入BFS的队列中 ll.add(j); control[i][j] = true; } } } } } for (int i=1;i<=100;i++){//按照顺序输出 for (int j=1;j<=100;j++){ if (i!=j){ if (control[i][j]){ pw.println(i+" "+j); } } } } pw.close(); } }
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 906原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 710原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 903原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 853原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 958原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 903原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 715原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 865原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 742原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1007原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1206原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 657原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 693原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 890原创文章转载请注明出处 摘要:模拟 , 数学分析 ... -
USACO - 2.1.5 - Hamming Codes
2012-08-18 19:22 779原创文章转载请注明出处 摘要:枚举、暴力 ...
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始