首页 > 其他分享 >洛谷 P1080 [NOIP2012 提高组] 国王游戏

洛谷 P1080 [NOIP2012 提高组] 国王游戏

时间:2024-08-02 17:25:54浏览次数:18  
标签:cnt 洛谷 NOIP2012 int res vector P1080 return size

一道非常有挑战性的题目(~太难了~)。

这题我们可以用贪心来做。

思路:

  1. 首先我们定义一个结构体 struct,里面放的是每个人左手和右手的数字。
  2. 接着我们需要一种排列方式,使得获得奖赏最多的大臣,所获奖赏尽可能的少;这句话听起来是不是听绕口?意思就是说得到奖赏数量最多,但加起来的总奖赏和最少;因此,我们可以定义一个自定义排序 cmp,使 a.l*a.r<b.l*b.r。
  3. 我们可以在定义两个 vector 数组 ans 和 t,ans 第 0 个值初始化成0,t 第  0 个值初始化成 1。
  4. 随后是高精度乘低精度和高精度除以低精度的函数。
  5. 最后再定义一个函数 compare,用来比较大小。
  6. 输入,注意:要先输入 f[0].l 和 f[0].r,表示国王的左手和右手。

AC CODE:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct stu{
	int l;
	int r;
}f[1005];
bool cmp(stu a,stu b){
	return a.l*a.r<b.l*b.r;
}
int n;
vector<int> ans(1,0);
vector<int> t(1,1);
inline vector<int> mul(vector<int> &a,int b){
	vector<int> res;
	int t = 0;
	int len = a.size();
	for(int i=0;i<len;i++){
		t+=a[i]*b;
		res.push_back(t%10);
		t/=10;
	}
	while(t){
		res.push_back(t%10);
		t/=10;
	}
	return res;
}
inline vector<int> div(vector<int> &a,int b){
	vector<int> res;
	int r = 0;
	int len = a.size();
	for(int i=len-1;i>=0;i--){
		r = 10*r+a[i];
		if(r>=b){
			res.push_back(r/b);
			r%=b;
		}else{
			res.push_back(0);
		}
	}
	vector<int> cnt;
	len = res.size();
	for(int i=len-1;i>=0;i--){
		cnt.push_back(res[i]);
	}
	while((cnt.back()==0)&&(cnt.size()>1)){
		cnt.pop_back();
	}
	return cnt;
}
inline int compare(vector<int> &a,vector<int> &b){
	int lenA = a.size();
	int lenB = b.size();
	if(lenA!=lenB){
		int t = lenA-lenB;
		return t;
	}else{
		for(int i=lenA-1;i>=0;i--){
			if(a[i]!=b[i]){
				int t = a[i]-b[i];
				return t;
			}
		}
		return 0;
	} 
}
int main(){
	cin>>n;
	cin>>f[0].l>>f[0].r;
	for(int i=1;i<=n;i++){
		cin>>f[i].l>>f[i].r;
	}
	sort(f+1,f+1+n,cmp);
	t = mul(t,f[0].l);
	for(int i=1;i<=n;i++){
		vector<int> res = div(t,f[i].r);
		if(compare(ans,res)<0){
			ans = res;
		}
		t = mul(t,f[i].l);
	}
	int len = ans.size();
	for(int i=len-1;i>=0;i--){
		cout<<ans[i];
	}
	cout<<endl;
	return 0;
}

标签:cnt,洛谷,NOIP2012,int,res,vector,P1080,return,size
From: https://blog.csdn.net/wang__1233/article/details/140824096

相关文章

  • 洛谷-P3869 [TJOI2009] 宝藏
    Abstract传送门本题是状态压缩+记忆化BFS的典型例子。Idea要求从出发点到终点的最短步数,BFS自然是首选的方法,那么,如何构造搜索的每一个节点呢?考虑到机关的数量比较小,最多10种,我们可以考虑用状态压缩去描述机关当前的状态,然后再记录当前的横纵坐标,以及行走的步数即可。值得......
  • 洛谷 P1052 [NOIP2005 提高组] 过河
    原题https://www.luogu.com.cn/problem/P1052题目描述在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:1,⋯,L......
  • 洛谷P3161 [CQOI2012] 模拟工厂 贪心策略的思考
    P3161[CQOI2012]模拟工厂传送门:模拟工厂问题描述:初始的生产力和商品分别为1和0。每一个时刻可以选择两个动作:生产力+1或者生产生产力数量的商品。现在有很多个订单,每个订单有三个部分:时间t,需要多少商品p,可以获得的价值v。现在需要决定各个时刻的动作选择,以及订单是否接取,以期......
  • 洛谷题单指南-前缀和差分与离散化-P3029 [USACO11NOV] Cow Lineup S
    原题链接:https://www.luogu.com.cn/problem/P3029题意解读:不同的坐标位置有不同种类的牛,要计算一个最小的区间,包括所有种类的牛。解题思路:由于坐标位置不连续,并且数值范围较大,因此需要离散化处理,将坐标处理成1~n连续分布由于种类编号数值范围也比较大,也需要离散化处理,去重后的......
  • 洛谷P2801 教主的魔法之分块板子
    洛谷P2801题解传送锚点摸鱼环节教主的魔法题目描述教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是\(N\)个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为\(1,2,\ldots,N\)。每个人的身高一开始都是不超过\(1000\)......
  • 洛谷 B3612 【深进1.例1】求区间和
    "这道题也太水了吧,模拟就行了!""数据范围...""好像不行呀""呜呜~~TLE!"献上暴力代码!#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,a[N],m;signedmain(){ios::sync_with_stdio(0);cin.tie(0);......
  • 洛谷题单指南-前缀和差分与离散化-P4552 [Poetize6] IncDec Sequence
    原题链接:https://www.luogu.com.cn/problem/P4552题意解读:对一组数字序列,进行若干次区间+1或者-1操作,最终使得所有数字一样,计算最少的操作次数,以及能得到多少种不同序列。解题思路:要使得序列每一个数字都相同,则其差分除了第一项之外其余项都是0。因此,问题转化为:给定一个差分数......
  • 洛谷题单指南-前缀和差分与离散化-P2882 [USACO07MAR] Face The Right Way G
    原题链接:https://www.luogu.com.cn/problem/P2882题意解读:一个有F、B组成的序列,每次可以翻转k个连续子序列,翻转:F->B,B->F,计算最少翻转多少次可以将序列都变成F,并求相应的k。解题思路:为方便处理,设F为1,B为01、朴素做法枚举k:1~n  枚举序列,一旦遇到0,就将连续k个字符翻转,如果可......
  • 洛谷P2696之慈善的约瑟夫——题解
    洛谷P2696题解[传送锚点](P2696慈善的约瑟夫-洛谷|计算机科学教育新生态(luogu.com.cn))比不过大佬,从蒟蒻做起选择比较水有意思的解法——用队列模拟(还是窝太弱了)正片开始考虑队列模拟,因为每次都是假的剔除,所以我们的目标是找到每回游戏的最终存活者。将不被剔除,......
  • 洛谷-P1171-售货员的难题
    Abstract传送门也算是状压dp模板题?不过这个数据给的有点阴间了,空间不够用,需要搞一个奇妙的优化。idea所谓状压,就是用数字表示当前状态,比如说0110100这个数字,我们可以把01分别看作是是否到达过第i个点的标记。那么我们可以用dp[i][j]表示第i个状态下,快递员到达j......