邯郸营销型网站建设,公司网站建设调研问卷,网络营销的工作岗位,网站建设收费题目描述
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数#xff0c;国王自己也在左、右手上各写一个整数。然后#xff0c;让这 n 位大臣排成一排#xff0c;国王站在队伍的最前面。排好队后#xff0c;所有的大…题目描述
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数国王自己也在左、右手上各写一个整数。然后让这 n 位大臣排成一排国王站在队伍的最前面。排好队后所有的大臣都会获得国王奖赏的若干金币每位大臣获得的金币数分别是排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏所以他想请你帮他重新安排一下队伍的顺序使得获得奖赏最多的大臣所获奖赏尽可能的少。注意国王的位置始终在队伍的最前面。 输入
第一行包含一个整数 n表示大臣的人数。
第二行包含两个整数 a 和 b之间用一个空格隔开,分别表示国王左手和右手上的整数。均小于 10000
接下来 n 行每行包含两个整数 a 和 b之间用一个空格隔开分别表示每个大臣左手和右手上的整数。均小于 10000
输出
输出一个整数表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 样例输入
3
1 1
2 3
7 4
4 6
样例输出
2 数据规模与约定
时间限制1 s
内存限制256 M
100% 的数据保证 1≤n≤1000
解题分析
本题需要采用一种微扰的思想去探索贪心算法的实现如何才能排队让得到最多的钱的大臣得到的钱尽可能地少呢不妨这样去思考我们假设这些大臣排成了C0C1C2C3......CiCi1, .......Cn其中C0就是国王国王一定要排在第一位的所以不用去考虑他。不妨假设Ci1这个大臣得到的奖赏就是最多的那么他得到的钱Pi1a0*a1*a2*.....*ai1/bi1在我们的假设下这个钱一定会大于等于其他人能够得到的钱接下来我们考虑对整个队列进行一个“微扰”就是说我们把Ci和Ci1两个人调换一下位置在这样的调换位置中可以发现整个队列中除了Ci和Ci1其他所有人获得的奖赏都没有发生任何的改变。而Ci1得到的钱变成了a0*a1*...*ai-1*ai1/bi1,Ci得到的钱变成了a0*a1*.....*ai-1*ai1*ai/bi可以发现Ci1得到的钱变少了而Ci得到的钱和原来相比变多了这个时候只需让a0*a1*.....*ai-1*ai1*ai/bia0*a1*a2*.....*ai1/bi1也就是ai1*bi1ai*bi那么Ci得到的钱就小于原来Ci1得到的钱。也就是说当ai1*bi1ai*bi的时候我们让Ci1和Ci交换位置这个时候这两个大臣得到的钱一定会比原来更少换言之如果我们让左右手相乘的数小的人排前面大的人排后面那么得到奖赏最多的大臣得到的钱是所有排列情况中最少的。
这段程序使用了贪心算法来解决问题。
首先程序读取输入数据包括大臣的人数n以及每个人的左手和右手上的整数。
然后程序定义了一个cmp函数来作为排序比较函数。该函数比较两个大臣的获奖金币数根据题目要求返回较小的金币数对应的大臣排在前面。
接下来程序通过调用sort函数对大臣进行排序排序的依据是cmp函数的返回结果。这样就得到了一个重新排列后的队伍使得获得奖赏最多的大臣所获得的金币数尽可能少。
然后程序初始化maxSum为一个较小的负无穷值p为国王左手上的整数。
接着程序使用循环遍历重新排列后的队伍中的每个大臣。对于每个大臣程序计算其获奖金币数并更新maxSum的值。具体的计算方法是将p除以该大臣右手上的整数并将结果与maxSum比较取较大值作为新的maxSum。然后程序将p乘以该大臣左手上的整数为下一个大臣的计算做准备。
最后程序输出maxSum即重新排列后的队伍中获得奖赏最多的大臣所获得的金币数。
该算法的时间复杂度为O(nlogn)其中n为大臣的人数。这是因为排序的时间复杂度为O(nlogn)而循环遍历大臣的时间复杂度为O(n)。
代码实现
#include iostream
#include algorithm
#define MAXN 10005
using namespace std;
int n,a[MAXN],b[MAXN],c[MAXN];
bool cmp(int i,int j){if(a[i]*b[i]a[j]*b[j]){return 1;}return 0;
}
int main(){scanf(%d,n);for(int i0;in;i){scanf(%d %d,a[i],b[i]);}for(int i0;in;i){c[i]i;}sort(c1,cn1,cmp);int maxSum-1e9,p1*a[0];for(int i1;in;i){int tempp/b[c[i]];maxSummax(maxSum,temp);p*a[c[i]];}printf(%d\n,maxSum);return 0;
}
