题解 | #装备合成#

装备合成

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;
}
全部评论

相关推荐

offer多多的六边形战士很无语:看了你的博客,感觉挺不错的,可以把你的访问量和粉丝数在简历里提一下,闪光点(仅个人意见)
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-29 12:19
点赞 评论 收藏
分享
评论
点赞
收藏
分享
正在热议
# 25届秋招总结 #
442240次浏览 4509人参与
# 春招别灰心,我们一人来一句鼓励 #
41913次浏览 531人参与
# 阿里云管培生offer #
120216次浏览 2219人参与
# 地方国企笔面经互助 #
7961次浏览 18人参与
# 同bg的你秋招战况如何? #
76585次浏览 561人参与
# 虾皮求职进展汇总 #
115499次浏览 886人参与
# 北方华创开奖 #
107424次浏览 599人参与
# 实习,投递多份简历没人回复怎么办 #
2454609次浏览 34856人参与
# 实习必须要去大厂吗? #
55761次浏览 961人参与
# 提前批简历挂麻了怎么办 #
149889次浏览 1977人参与
# 投递实习岗位前的准备 #
1195913次浏览 18548人参与
# 你投递的公司有几家约面了? #
33205次浏览 188人参与
# 双非本科求职如何逆袭 #
662189次浏览 7394人参与
# 如果公司给你放一天假,你会怎么度过? #
4751次浏览 55人参与
# 机械人春招想让哪家公司来捞你? #
157622次浏览 2267人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
11535次浏览 284人参与
# 发工资后,你做的第一件事是什么 #
12682次浏览 62人参与
# 工作中,努力重要还是选择重要? #
35793次浏览 384人参与
# 参加完秋招的机械人,还参加春招吗? #
20120次浏览 240人参与
# 我的上岸简历长这样 #
452000次浏览 8088人参与
# 实习想申请秋招offer,能不能argue薪资 #
39289次浏览 314人参与
# 非技术岗是怎么找实习的 #
155866次浏览 2120人参与
牛客网
牛客企业服务