题解 | #装备合成#

装备合成

https://ac.nowcoder.com/acm/problem/200211

思路:

三分,三分要满足函数是先增后减或者先减后增的,这里可以三分用第一个方案的次数,假设第一个方案用了n次,那么第二个方案的个数就是min( (x-2n)/4 , y-3n ),对于单调性的证明,参考下面的博客。

https://blog.csdn.net/RunningBeef/article/details/113836764?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.pc_relevant_default&spm=1001.2101.3001.4242.1&utm_relevant_index=3

代码:

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int x,y;

int check(int f){
	return f+min((x-f*2)/4,(y-3*f));//总件数
}

int main() {
	int t;
	cin>>t;
	while(t--) 
	{
        scanf("%d%d",&x,&y);
        int l=0,r=min(x/2,y/3);//r最大就是都用第一种方案
        while(l<r)
        {
        	int mid1=l+(r-l)/3;
        	int mid2=r-(r-l)/3;
        	
			if(check(mid1)>check(mid2))
			{
				r=mid2-1;
			}
			else l=mid1+1;
		}
		
		cout<<check(l)<<endl;
		
	}

	return 0;
}
全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务