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=

随便看看

ES系列二、Mac 通过docker搭建ELK日志收集系统

#检查是否安装了elkdockerimages#清理以前版本的dockerrmi$#安装elk 6.8.0版本的docker pullslasticsearch:6.8.0 dockerpullskibana:68.0dockerpullogstash:68.00#检查dockerimages2是否查看拉取的ElasticSearch:操作命令:docker...

svn常见问题汇总

要添加到版本库,必须更新工作副本中的文件。5.更新时,系统会提示您文件冲突,将工作副本中的文件与服务器中的文件进行比较“当版本管理系统更改计算机上的工作副本时”,它会尝试将您的意图写入计算机上的日志文件,因此日志文件记录可能与您的上次工作状态不一致。Subversion客户端将在提交内容之前在本地工作副本中写入日志。首先删除隐藏文件夹中tmp下的临时文件。服...

VMware vSphere 7.0 安装教程

插入CD,启动系统并等待安装包加载映像,按Enter等待协议条款,同意,然后按F11进行磁盘分区管理。由于测试环境的原因,只有一个硬盘,直接按Enter键进入键盘布局,选择默认设置,按Enter键设置根帐户的密码,输入完成后按Enter键确认安装,按F11键等待安装完成,取出安装CD,重新启动后按Enter重新启动系统,正在加载到系统中…请确保已导入磁盘。错...

关于WINFORM中输入法的设置

关于WINFORM(转移到)John Suna的专栏开发中输入方法的设置,它碰巧遇到了这种问题。网络真的很好:)这是文本集。感谢作者的辛勤工作给您带来的便利。在WINFORM中,我们经常遇到这样的问题:文本输入框中的输入法被禁用或总是更改为全宽输入法。查阅相关数据后,总结如下:(1)Control.ImeMode属性:获取或设置控件的输入方法编辑器模式。此模...

axios 学习文档

Axios是一个基于承诺的HTTP库,可以在浏览器和node.js中使用。执行POST请求axis.POST.then。接住执行多个并发请求函数getUserAccount(){returnaxios.get;}函数getUserPermissions(){returnaxios.get;}全部承诺。然后axios API可以通过传递相关配置来请求axios...

图论介绍(Graph Theory)

G-v具有比G更多的连通分支,因此v被称为G的截断点G-e具有比G多的连通分支。定理:连通图G,其中e是桥e不属于G的任何环有顶点u,v,使得任何路径u-v都通过e连通图G;而w是存储在顶点u,v处的割点,使得任意路径u-v通过w定义:顶点之间的距离x-y:所有x-y路径的最小长度。...