Codeforces 346C Number Transformation II 构造

Codeforces 346C Number Transformation II 构造

大家好,又见面了,我是全栈君。

题目链接:点击打开链接

= = 990+ms卡过

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 100010
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define ll int
ll n,m,k,a,b;
ll x[N];
bool cmp(ll z,ll y){return z>y;}
set<int>myset;
set<int>::iterator p;
int main(){
	ll i,j;
	while(cin>>n){
		myset.clear();
		for(i=1;i<=n;i++)scanf("%d",&j),myset.insert(j);
		cin>>a>>b;
		if(a==b){puts("0");continue;}
		n = myset.size();
		i = 1;
		for(p = myset.begin(); p!=myset.end(); p++,i++)x[i] = *p;
		sort(x+1,x+1+n,cmp);
		ll step = 0;
		ll l = 1;
		while(x[l]>a && l<=n)l++;
		while(x[l]>(a>>1) && (a-x[l])>(a-b))l++;
		if(l>n){cout<<a-b<<endl;continue;}

		while(a!=b){
			step++;
			ll now = 1, cha = a-b;

			for(i = l;i<=n;i++)
			{
				if(now>=x[i])break;
				ll tmp = a-((a/x[i])*x[i]);
				if(tmp<=now || tmp>cha)continue;
				now = tmp;
			}
			a-=now;
			while(x[l]>a&&l<=n)l++;
			while(x[l]>(a>>1) && (a-x[l])>cha)l++;
			if(l>n)break;
		}
		cout<<step+a-b<<endl;
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115207.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • box-shadow(盒子阴影)

    box-shadow(盒子阴影)深入理解css3新增属性之box-shadow盒子阴影,它可以向框添加一个或多个阴影

  • 微软校招试题

    把微软的这个笔试题贴出来,纯粹是为了方便大家学习交流,相信微软不会那么小气来追究我的责任吧。确实觉得微软出的这些题都不错,虽然只有20道选择,但是考察的面很全,数据结构,网络,算法,操作系统,概率等等

    2021年12月25日
  • XXX测试用例设计?XXX怎么测试?(行李箱、电梯、水杯、笔、椅子)

    XXX测试用例设计?XXX怎么测试?(行李箱、电梯、水杯、笔、椅子)建议回答内容:功能测试(单个功能、逻辑业务/功能交互)、界面测试、易用性测试、兼容性测试、安全性测试、性能测试行李箱我不知道这个行李箱的具体需求,所以会以我认知的行李箱来思考从功能测试来考虑的话,拉杆箱大小、厚度、容量、各个面(包括拉杆面、脚轮面)承重拉杆承重是否符合质检标准;超出容量、超出承重会有什么影响;拉杆的伸缩收回是否灵活;箱子的开锁解锁是否方便安全;界面测试,我会考虑箱子的材质、颜色、花纹、形状是否符合要求;箱子吊牌logo是否正确易用性方面,箱子拉杆手把是否易握防滑、箱子

  • 牛客国庆集训派对Day6 I.清明梦超能力者黄YY(树剖)「建议收藏」

    牛客国庆集训派对Day6 I.清明梦超能力者黄YY(树剖)「建议收藏」题目:https://www.nowcoder.com/acm/contest/206/I正难则反。问你倒数第k次的颜色,正着来搞不定,那就转换成“倒着来的第k次”。使用树剖将这棵树丢进线段树里,不维护染色,而是维护更新的次数(因为除了倒数第k次的颜色,其他的根本没用啊!!!),然后把区间最小值pushUp到树顶。更新完染色次数之后,用树顶来判整个区间里是否存在已经被更新了k次的节点,如果…

  • 解决Centos/Redhat,命令不存在

    解决Centos/Redhat,命令不存在

  • idea2021永久激活码【2021.7最新】

    (idea2021永久激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html65MJGLILER-eyJsaWNlbnNlSWQi…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号