鹤壁 网站建设,wordpress api 路径,简述企业网站建设的目的有哪些,手机商城页面设计[NOIP2012 提高组] 国王游戏
题目描述
恰逢 H 国国庆#xff0c;国王邀请 n n n 位大臣来玩一个有奖游戏。首先#xff0c;他让每个大臣在左、右手上面分别写下一个整数#xff0c;国王自己也在左、右手上各写一个整数。然后#xff0c;让这 n n n 位大臣排成一排…[NOIP2012 提高组] 国王游戏
题目描述
恰逢 H 国国庆国王邀请 n n n 位大臣来玩一个有奖游戏。首先他让每个大臣在左、右手上面分别写下一个整数国王自己也在左、右手上各写一个整数。然后让这 n n n 位大臣排成一排国王站在队伍的最前面。排好队后所有的大臣都会获得国王奖赏的若干金币每位大臣获得的金币数分别是排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏所以他想请你帮他重新安排一下队伍的顺序使得获得奖赏最多的大臣所获奖赏尽可能的少。注意国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 n n n表示大臣的人数。
第二行包含两个整数 a a a 和 b b b之间用一个空格隔开分别表示国王左手和右手上的整数。
接下来 n n n 行每行包含两个整数 a a a 和 b b b之间用一个空格隔开分别表示每个大臣左手和右手上的整数。
输出格式
一个整数表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
样例 #1
样例输入 #1
3
1 1
2 3
7 4
4 6样例输出 #1
2提示
【输入输出样例说明】
按 1 1 1、 2 2 2、 3 3 3 这样排列队伍获得奖赏最多的大臣所获得金币数为 2 2 2
按 1 1 1、 3 3 3、 2 2 2 这样排列队伍获得奖赏最多的大臣所获得金币数为 2 2 2
按 2 2 2、 1 1 1、 3 3 3 这样排列队伍获得奖赏最多的大臣所获得金币数为 2 2 2
按$ 2$、 3 3 3、$1 $这样排列队伍获得奖赏最多的大臣所获得金币数为 9 9 9
按 3 3 3、 1 1 1、$2 $这样排列队伍获得奖赏最多的大臣所获得金币数为 2 2 2
按$ 3$、 2 2 2、 1 1 1 这样排列队伍获得奖赏最多的大臣所获得金币数为 9 9 9。
因此奖赏最多的大臣最少获得 2 2 2 个金币答案输出 2 2 2。
【数据范围】
对于 20 % 20\% 20% 的数据有 1 ≤ n ≤ 10 , 0 a , b 8 1≤ n≤ 10,0 a,b 8 1≤n≤10,0a,b8
对于 40 % 40\% 40% 的数据有$ 1≤ n≤20,0 a,b 8$
对于 60 % 60\% 60% 的数据有 1 ≤ n ≤ 100 1≤ n≤100 1≤n≤100
对于 60 % 60\% 60% 的数据保证答案不超过 1 0 9 10^9 109
对于 100 % 100\% 100% 的数据有 1 ≤ n ≤ 1 , 000 , 0 a , b 10000 1 ≤ n ≤1,000,0 a,b 10000 1≤n≤1,000,0a,b10000。
NOIP 2012 提高组 第一天 第二题
思路
交换任意两个大臣时只会影响他们各自的金币数而不会影响他们之前和之后的大臣的金币数因此可以考虑贪心对比两个大臣交换前后的金币。假设相邻的两个大臣中其左右手分别为 a1b1a2b2之前所有人的左手乘积总和为 sum可得交换前为 sum * a1 / b2交换后为 sum * a2 / b1若存在交换前 交换后可推出 a1 * b1 a2 * b2此时交换两大臣可使获得金币减少。即对大臣左右手金币的乘积进行上升排列即是最优方法。
AC代码
#includemap
#includeset
#includestack
#includecmath
#includequeue
#includestring
#includebitset
#includecstring
#includeiostream
#includealgorithm
#includenumeric
#define endl \n
using namespace std;typedef long long ll;
typedef pairint, intPII;
const int N3e510;
const int MOD998244353;
const int INF0X3F3F3F3F;
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,-1,1,-1,1,-1,1};
const int M 1e6 10;ll x[N] {1}, y[N];
ll n;struct stu
{ll l, r;bool operator (const stu u)const {return l * r u.l * u.r;}
}s[N];
ll cnt 1;void chen(ll u)
{ll tem 0;for(int i 0; i cnt; i ) x[i] * u;//左手相乘for(int i 0; i cnt; i ) {tem x[i];x[i] tem % 10;tem / 10;}while(tem ! 0){x[cnt] tem % 10;cnt ;tem / 10;}
}void chu(ll u)
{ll tem 0;for(int i cnt - 1; i 0; i --){tem tem * 10 x[i];y[i] tem / u;tem % u;}
}void print()
{ll tem cnt;if(n 1) cout s[0].l / s[1].r endl;else {while(y[tem] 0){tem --;if(tem -1){cout 1;return ;}}for(int i tem; i 0; i --){cout y[i];}}}
int main()
{cin n;for(int i 0; i n; i ){ll a, b;cin s[i].l s[i].r;}sort(s 1, s 1 n);for(int i 0; i n; i ){chen(s[i].l);}chu(s[n].r);print();return 0;
}
