VIJOS 1779 国王游戏
发布日期:2022-02-05 18:27:33 浏览次数:6 分类:技术文章

本文共 2247 字,大约阅读时间需要 7 分钟。

描述

恰逢H国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这n位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

格式

输入格式

第一行包含一个整数n,表示大臣的人数。 
第二行包含两个整数a和b,之间用一个空格隔开,分别表示国王左手和右手上的整数。接下来n行,每行包含两个整数a和b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

输出格式

输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例

样例输入

3 1 1 2 3 7 4 4 6

样例输出

2

限制

每个测试点1s

提示

对于20%的数据,有1≤ n≤ 10,0 < a、b < 8; 
对于40%的数据,有1≤ n≤20,0 < a、b < 8; 
对于60%的数据,有1≤ n≤100; 
对于60%的数据,保证答案不超过10^9; 
对于100%的数据,有1 ≤ n ≤1,000,0 < a、b < 10000。

来源

Noip2012提高组复赛Day1T2



去年这题按右手排序骗了45好像。。

恩 其实这是一个贪心题

USACO 50题精选中有一个按加法排序的

这个题需要按乘法排序

如何考虑


假设前i个左手乘积X

相连两个

第一个

1.A B

第二个

2..C D


则按 1 2 的顺序排

X/B  X*A/D 

将两人互换后 

X/D  X*C/B


显然

 X*A/D>X/D

X*C/B>X/B


我们只需讨论X*A/D和X*C/B的关系 就可以确定这两种哪一种更好

我们发现 X*A/D和X*C/B==>A/D和C/B

A/D和C/B 同乘B*D 变成 A*B和C*D

A/D<C/B充要条件是A*B<C*D (A,B,C,D都为正整数)


所以按乘积从小到大排序 然后统计每一个大臣的获益 最大值输出即可


有的同学直接输出的最后一个大臣的 好像有一个点WA。。。

原因不明 个人感觉不一定在最后才取最值



用到了高精*单精  高精/单精

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=1111;int m,z[lim];struct self{int x,y,z;}s[lim];int l[lim];int a,b,c,d;int cmp(self a1,self a2){
       
return a1.z
int a;
cout<
for(a=s[0]-1;a>=1;a--)
{
if(s[a]<1000)cout<<0;
if(s[a]<100)cout<<0;
if(s[a]<10)cout<<0;
cout<
}
cout<
int a;
for(a=1;a<=1000;a++)
if(s[a]>=10000)
{
s[a+1]=s[a+1]+s[a]/10000;
s[a]%=10000;
s[0]=max(s[0],a+1);
}}void cheng(int s[lim],int x){
int a;
for(a=1;a<=s[0];a++)s[a]*=x;
jinwei(s);}void copy(int f[lim],int t[lim]){
int a;
for(a=0;a<=f[0];a++)t[a]=f[a];}bool dayu(int f[lim],int t[lim]){
int a;
if(f[0]>t[0])return true;
if(f[0]
for(a=f[0];a>=1;a--)
{
if(f[a]>t[a])return true;
if(f[a]
}
return false;}void querymin(int s[lim],int x){
int t[lim]={0},w[lim],a,b,lim;
copy(s,w);
for(a=w[0];a>=1;a--)
{
t[a]=w[a]/x;
if(t[a]!=0)t[0]=max(t[0],a);
w[a]=w[a]-t[a]*x;
w[a-1]=w[a]*10000+w[a-1];
w[a]=0;
}
if(dayu(t,z))copy(t,z);}int main(){
scanf("%d",&m);
m++;
for(a=1;a<=m;a++)
{
scanf("%d%d",&s[a].x,&s[a].y);
s[a].z=s[a].x*s[a].y;
}
sort(s+2,s+m+1,cmp);
l[1]=s[1].x;l[0]=1;
for(a=2;a<=m;a++)
{
querymin(l,s[a].y);
cheng(l,s[a].x);
}
print(z);
return 0;}


转载地址:https://blog.csdn.net/li412302070/article/details/14445427 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VIJOS 1740 聪明的质检员
下一篇:VIJOS 1737 选择客栈

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.173.107.153]2022年08月16日 12时17分49秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

tensorflow2之数学运算 2019-12-12 23:02:25
如何构建指标体系--笔记 2019-12-12 23:02:25
LaTeX数学表达式 2019-12-12 23:02:25
tensorflow2之切片 2019-12-12 23:02:25
AirFlow之安装 2019-12-12 23:02:24
实时数据同步 2019-12-12 23:02:24
数据库概况查阅 2019-12-12 23:02:24
hive metastore为MySQL时的中文乱码问题 2019-12-12 23:02:24
白噪音及其检验 2019-12-12 23:02:23
单因子方差分析 2019-12-12 23:02:23
Elasticsearch笔记 2019-12-12 23:02:22
DW及建模 2019-12-12 23:02:23
非参数检验 2019-12-12 23:02:22
【转载】概率分布的自由度 2019-12-12 23:02:22
python download不带文件名的文件/文件流 2019-12-12 23:02:22
假设检验是单侧还是双侧 2019-12-12 23:02:21
【转载】CDH下线与上线主机 2019-12-12 23:02:20
抽样分布定理 2019-12-12 23:02:21
二值分类器的优劣判断 2019-12-12 23:02:18
Python未定义参数的传参与识别 2019-12-12 23:02:19