codevs 1198 国王的游戏

摘要:
有一位国王站在队列的开头,左手拿着数字,右手拿着数字。然后有n个人左手拿着一个数字,左手拿一个数字。然后,他随机对n个人进行排序,将第i个人的权重值定义为前一个人的所有左手数字除以第i个人右手数字的乘积,并询问如何排序,以使n个人的最大权重值最小,并输出该权重值。解决方案:问题是如何排序以最小化最大重量。然后我们需要知道排序条件。为了找出这个条件,我们考虑第i个人和第i+1个人。解:设a和b是第i个人的左手和右手数字,c和d是第一个

题意:

有个国王站在一个队列的开头,左右手各有一个数字,然后有n个人左右手也各有一个数字,然后把这n个人随便排序,定义第i个人的权值为前面所有的人左手数字乘积除以第i个人右手的数字,问的是怎么排序使得这n个人中最大的权值最小,输出这个权值。

题解:

问题是怎么排序使得最大权值最小,那我们就需要知道排序的条件,为了找出这个条件,我们考虑第i个人和第i+1个人。

解:设a,b为第i个人左右手的数字,c,d为第i+1个人左右手的数字,s为第1个人到第i-1个人左手数字的乘积

可以得出第i个人的权值为wi = s / b 第i+1个人的权值为 wi+1 = s * a / d,那么最大值为max (s / b, s * a / d)

可以得出换了位置之后第i+1个人的权值为 wi+1 = s / d 第i个人的权值为 wi = s * c / b,那么最大值为max (s / d, s * c / b)

假设换了位置更优 那么 max (s / d, s * c / b) < max (s / b, s * a / d)

假设s / d > s * c / b 那么 s / d < max (s / b, s * a / d),很显然的是s * a / d > s / d,那么根据s / b > s / d 可以得出d > b 但与条件(b > c * d)矛盾不成立

假设s / d < s * c / b 那么 s * c / b < max(s / b, s * a / d) 但是 s * c / b > s / b所以不考虑,那么由 s * c / b < s * a / d 得出 a * b < c * d 符合条件 b < c * d

得出结论:按照左右手乘积从小到大排序一定最优

因为我很懒就没有写高精度了QAQ

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e3 + 7;
#define ll unsigned long long
int n;
ll sl, sr;
struct node {ll L, R;} p[N];

bool cmp (node a, node b) {
	return a.L * a. R < b.L * b.R;
}

int main () {
	scanf ("%d", &n);
	cin >> sl >> sr;
	for (int i = 1; i <= n ;++i) {
		cin >> p[i].L >> p[i].R;
	}
	sort (p + 1, p + 1 + n, cmp);
	ll sum = sl, maxi = 0;
	for (int i = 1; i <= n; ++i) {
		maxi = max (maxi, sum / p[i].R);
		sum = sum * p[i].L;
	}
	cout << maxi << endl;
	return 0;
}

  

总结:

这种按照某种方式变化的题型,需要我们找到变化的最优条件,不妨设一设,搞一搞总会搞出来的~

免责声明:文章转载自《codevs 1198 国王的游戏》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇python 高级部分fedora19安装后,需要安装的一些必备的软件包下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

uniApp之 顶部选项卡

为了在uniapp插件中创建类似于信息应用程序模板的功能,使用了官方的组件刷。起初,它无法滚动。后来,我看了一下官方网站,说有必要添加“滚动视图”标签,以记录第一次使用uniapp的应用程序。首先,在顶部制作一个选项卡,因为我只有两个项目,所以我将它们直接写入视图标记中{item.label}}然后编写以下内容。单击和滑动可以切换选项卡,所选样式:curre...

【Lua】使用随机数(转)

游戏中有一个用于创建角色的随机命名功能,它使用随机数。我在网上找到一篇关于在Lua使用随机数的文章。标记它。Lua需要两个函数来生成随机数:数学。randomseed,数学。数学随机种子接收整数n作为随机序列种子。将系统时间视为随机种子是很自然的,也就是说,数学随机——然后连续生成i=1,5do打印结束的随机数,但问题出现了。如果程序在短时间内运行几次,您得...

【转】 中兴OLT-C300常用命令

在当前的C220版本中,ONU类型名称在GPON和EPON中应该是唯一的。这里我们使用“ZTEG-F620”。ZXAN#ponZXAN#onu-typegponZTEG-F620描述4ETH,2POTSZXAN#onu-ifZTEG-F620eth_0/1-4ZXAN#onon-ifZTEG-F620pots_0/1-2ZXAN#on u type attr...

CentOS7 复制文件夹和移动文件夹

CentOS7在Linux中复制、移动和删除文件的命令有:cp、mv、rm I。文件复制命令cp命令格式:cp[-adfilprsu]源文件(source)目标文件(destination)cp[option]source1source2source3…directory参数描述:-a:指存档,即复制所有目录-d:如果源文件是连接文件(linkfile...

愿你走出半生,归来仍是Java Parser

几天前,我的一个朋友给了我一个Haskell问题嘿,MK。假设我有一个BNF,我在Haskell中有一个这个BNF的解析器。现在,我想为这个BNF换一条线。是否有任何方法可以在不接触BNF解析器代码的情况下扩展BNF解析器?让我们想想,这个x是什么样的变体?请记住,传入的参数不是self,而是super。好了,openrecursion已经准备好了,剩下的是...

解读阿里官方代码规范

作者将解释此代码规范的一些细节,包括作者的观点和想法,这些可以作为此代码规范扩展。该公众号共发表了五篇文章。这篇文章是一个集合,之前的一些文章已经过修改。在实际的编程过程中,作者可能会对类名的风格更加激进。根据阿里巴巴的规范,类名应该使用UpperCamelCase样式,并且必须遵循驼峰形式。但是,有以下例外:实际上,DO/BO/DTO/VO可能有UserV...