题目描述

恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右

手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排

成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每

位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右

手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,

使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

输入输出格式

输入格式:

第一行包含一个整数 n,表示大臣的人数。

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

接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手

和右手上的整数。

输出格式:

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

金币数。

输入输出样例

输入样例#1:

3
1 1
2 3
7 4
4 6
输出样例#1:

2

说明

【输入输出样例说明】

按 1、2、3 号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 1、3、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 2、1、3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 2、3、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9;

按 3、1、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 3、2、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9。

因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。

【数据范围】

对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;

对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;

对于 60%的数据,有 1≤ n≤100;

对于 60%的数据,保证答案不超过 109;

对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

NOIP 2012 提高组 第一天 第二题

--------------------------------------------

二分不行,那就贪心了。

从头开始不方便,我就先从队伍最后的人开始。W=S/(A*B)

(A*B)最大的人排在最后好,所以按(A*B)小到大排序,扫描即可

[这样好像不太严谨,最大的不一定在最后]

还有一种贪心思路:

考虑相邻的两个人,交换位置只会影响到他们两个人,(A*B)小的人在前好

-------------------------------------------------------------------------

因为规模太大,所以要用高精度!!!

高精乘和高精除。

然后就开始“证明”我的基础有多弱,先用一种“把不存在的项置为-1”的方式写,调了4个小时还不好,就开始封装结构体

除法,我只会累减,貌似tle了

----------

我的代码,洛谷re,vijos50分,哎哎哎哎哎哎

----------------------------------------------update2016-08-08-23:28:48----------------------------------------

补了一下高精度除单精度,直接模拟行了,高精度除高精度才要减,我太弱智了

现在ac

//关于高精
//倒着存 都是高精和低精 B取的低精最大值所以简化了一点
//小新chuInt-->B大g可能溢出
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=,B=1e4,W=,L=;
struct people{
int a,b,t;
}p[N];
bool cmp(people x,people y){
return x.t<y.t;
} struct big{
int size,d[L];
big(int a=):size(a){memset(d,,sizeof(int)*L);} };
bool bigger(big &a,big &b){
if(a.size>b.size) return true;
if(a.size<b.size) return false;
for(int i=a.size-;i>=;i++){
if(a.d[i]>b.d[i]) return true;
}
return false;
}
void copy(big &t,big &s){
t.size=s.size;
memcpy(t.d,s.d,sizeof(int)*L);
} void chengInt(big &a,int k){
int g=,i;
for(i=;i<a.size;i++){
int tmp=a.d[i]*k;
a.d[i]=(tmp+g)%B;
g=(tmp+g)/B;
}
while(g){
a.d[i++]=g%B; a.size++;
g/=B;
}
} void chuInt(big &a,int k){
int g=;
for(int i=a.size-;i>=;i--){
g=g*B+a.d[i];
a.d[i]=g/k;
g%=k;
}
while(a.d[a.size-]==) a.size--;
}
//原来的弱智方法
//void chuInt(big &a,int k,big &ans){
// while(noSmallInt(a,k))
// {jianInt(a,k);addInt(ans,1);}
//}
//void chuInt(big &a,int k,int &ans){
// while(noSmallInt(a,k))
// {jianInt(a,k);ans++;}
//}
int n;
big s,t,mx;
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=;i<=n;i++){scanf("%d%d",&p[i].a,&p[i].b); p[i].t=p[i].a*p[i].b;}
sort(p+,p+n+,cmp); s.d[]=p[].a;
for(int i=;i<=n;i++){for(int i=s.size-;i>=;i--)
copy(t,s);
chuInt(t,p[i].b);
if(bigger(t,mx)) copy(mx,t);
chengInt(s,p[i].a);
} for(int i=mx.size-;i>=;i--){
if(i!=mx.size-){
if(mx.d[i]<) cout<<"";
else if(mx.d[i]<) cout<<"";
else if(mx.d[i]<) cout<<"";
}
cout<<mx.d[i];
} }

最新文章

  1. 纯CSS打造好看的按钮样式
  2. java之多线程 二
  3. iOS开发--QQ音乐练习,后台播放和锁屏界面
  4. 洛谷P2015 二叉苹果树
  5. Java自定义Annotation,通过反射解析Annotation
  6. javascript基础笔记学习
  7. chrome console 调试xpath
  8. think queue 消息队列初体验
  9. SpringMVC源码情操陶冶-AbstractUrlHandlerMapping
  10. 深入Spring Boot:那些注入不了的Spring占位符(${}表达式)
  11. System.nanoTime与System.currentTimeMillis的区别(转)
  12. 最近学习的 Node.js 数组_函数
  13. JavaScript中的let和const
  14. Sqlserver自动优化
  15. 迈科DPI和运营商合作比较多
  16. Python实现鸢尾花数据集分类问题——基于skearn的NaiveBayes
  17. 让maven使用国内镜像和archetypeCatalog
  18. CAS使用心得
  19. 使用存储过程将Oracle数据批量导出为多个csv文件
  20. Centos75 安装 postgresql11

热门文章

  1. iPhone开发与cocos2d 经验谈
  2. Java入门第一章
  3. Atitit. null错误的设计 使用Optional来处理null
  4. Struts,spring,hibernate三大框架的面试
  5. Snap.svg – 现代 Web 开发必备的 JavaScript SVG 库
  6. 【单页应用巨坑之History】细数History带给单页应用的噩梦
  7. BFC总结
  8. CoreGraphics-基本图形绘制-直线、三角形、矩形、椭圆形、弧形
  9. OS的沙盒机制 --基础知识
  10. initialize和init以及load方法的区别与使用以及什么时候调用