about:blank
题解Problem 1 : leader谁是组长
问题描述 八中信息组需要选一个组长。信息组一共有n个人,分别用1到n编号,其中m个人参与了投票。得票数过半(票数大于m div 2)的人将被选为组长。 输入数据将告知这m个人分别将票投给了谁,请统计出谁将担任八中信息组的组长。
输入数据 第一行两个数n和m。 第二行有m个数,这些数都是不超过n的正整数,表明这m个人的选择。
输出数据 输出将被选为组长的人。如果没有人的票数过半,请输出-1。
输入样例7 47 7 2 7
输出样例7
时间限制 各测试点1秒
内存限制 你的程序将被分配10MB的运行空间
数据规模 1<=n<=maxlongint 1<=m<=10000题解: matrix67给出的方法是快排。然后一个O(m)的扫描即可。不过我没有用这种方法。正巧前几天看书看到了一道跟这题一模一样的题。据说曾经是ms的测试题。好了,回归正题,这题题意无非就是m个数,范围都在1-n中间,其实n是无用的。然后会有一个数出现的次数>m div 2。我们假设这个数的值是s,那么每次从这组数里去掉两个不同的数,因为是不同的数,则至多只可从这些数中去掉一个s,那么如此一直进行下去。去到找不到两个不同的数为止,则至少还会剩下一个s。当然,这是极端情况,大多数情况下应该会剩下不少s。复杂度为O(m)
Problem 2 : money最小花费
问题描述 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。
输入数据 第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。 以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。 最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
输出数据 输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
输入样例3 31 2 12 3 21 3 31 3
输出样例103.07153164
内存限制 你的程序将被分配40MB的运行空间
数据规模 1<=n<=2000题解: 比较明显的最短路径模型。不过刚转c++,我竟然不知道如何保留小数点后面的精度,所以这题就没有写精度。
Problem 3 : harm最小伤害
问题描述 把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。
输入数据 第一行输入一个正整数n。 以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。
输出数据 输出最小伤害值。
样例输入31 3 32 2 23 1 2
样例输出8
数据规模 n<=1000题解:这题是更加明显的动态规划。直接上代码……
Problem 4 : unique寻找代表
问题描述 八中一共有n个社团,分别用1到n编号。 八中一共有m个人,分别用1到m编号。每个人可以参加一个或多个社团,也可以不参加任何社团。 每个社团都需要选一个代表。我们希望更多的人能够成为代表。
输入数据 第一行输入两个数n和m。 以下n行每行若干个数,这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。
输出数据 输出最多的能够成为代表的人数。
样例输入4 41 2 01 2 01 2 01 2 3 4 0
样例输出3
数据范围 n,m<=200题解:2分图匹配,匈牙利算法。
posted on 2009-07-28 18:47 Vincent 阅读(694) 评论(0) 编辑 收藏 引用 所属分类: 数据结构与算法
Powered by: C++博客 Copyright © Vincent