NOIP2012国王游戏
题目描述
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右
手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排
成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每
位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右
手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,
使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
输入输出格式
输入格式:
第一行包含一个整数 n,表示大臣的人数。
第二行包含两个整数 a和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手
和右手上的整数。
输出格式:
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的
金币数。
输入输出样例
3
1 1
2 3
7 4
4 6
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];
} }
最新文章
- 纯CSS打造好看的按钮样式
- java之多线程 二
- iOS开发--QQ音乐练习,后台播放和锁屏界面
- 洛谷P2015 二叉苹果树
- Java自定义Annotation,通过反射解析Annotation
- javascript基础笔记学习
- chrome console 调试xpath
- think queue 消息队列初体验
- SpringMVC源码情操陶冶-AbstractUrlHandlerMapping
- 深入Spring Boot:那些注入不了的Spring占位符(${}表达式)
- System.nanoTime与System.currentTimeMillis的区别(转)
- 最近学习的 Node.js 数组_函数
- JavaScript中的let和const
- Sqlserver自动优化
- 迈科DPI和运营商合作比较多
- Python实现鸢尾花数据集分类问题——基于skearn的NaiveBayes
- 让maven使用国内镜像和archetypeCatalog
- CAS使用心得
- 使用存储过程将Oracle数据批量导出为多个csv文件
- Centos75 安装 postgresql11