• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AcWing 第一场周赛题解

开发技术 开发技术 3周前 (05-29) 11次浏览

A

暴力。或取 (A[],B[]) 中的最大值。

/*
 * AcWing week contest 1, A
 * Author: WuWh
 * Date: 2021/5/29
*/ 
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int n,m,a[205]={},b[205]={},d[205]={};
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];d[a[i]]=1;}
	cin>>m;
	for(int i=1;i<=m;i++){cin>>b[i];d[b[i]]=1;}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!d[a[i]+b[j]]){cout<<a[i]<<" "<<b[j]<<endl;return 0;}
	return 0;
}

B

显然答案具有单调性。考虑二分答案。

判断时,对于中位数之后的,只要小于 (mid) 就得补全(为了维护中位数始终不变)。

注意极大值的设定为 (2times 10^9) ,否则会被卡数据,还是比较恶心的。。。

/*
 * AcWing week contest 1, B
 * Author: WuWh
 * Date: 2021/5/29
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;long long k;
long long a[200050];
bool valid(long long x){
	long long res=0;
	for(int i=(n+1)>>1;i<=n;i++)if(a[i]<x)res+=x-a[i];
	return res<=k;
}
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	long long l=a[(n+1)>>1],r=2e9; // r 的取值很重要,卡数据! 
	while(l<r){
		int mid=(l+r+1)>>1;
		if(valid(mid))l=mid;
		else r=mid-1;
	}
	printf("%lldn",l);
	return 0;
}

程序员灯塔
转载请注明原文链接:AcWing 第一场周赛题解
喜欢 (0)