• 周二. 8月 16th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day13 C (二分+贪心)

admin

11月 28, 2021

题目链接在这里:Problem – C – Codeforces

网上很多说要用hall定理,emm还不太会用,不过这题可以贪心解决

就是feasible里面,每个男的只要选范围内离自己最远的那个女的就行

这里的贪心策略还是值得学习的

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MAX=1e6+5;
 5 LL n,l,a[MAX],b[MAX],c[MAX];
 6 LL fa[MAX];
 7 bool vis[MAX];
 8 bool feasible(LL x){
 9     LL i,j,k,an=0,low,high;
10     j=1,k=c[0];
11     for (i=1;i<=n;i++,j++,k++){
12         for (;j<=k && abs(a[i]-c[j])>x;j++);
13         for (;j<=k && abs(a[i]-c[k])>x;k--);
14     }
15     if (k<j) return false;
16     return true;
17 }
18 int main(){
19     LL i,j;
20     scanf("%lld%lld",&n,&l);c[0]=0;
21     for (i=1;i<=n;i++) scanf("%lld",a+i);
22     for (i=1;i<=n;i++) scanf("%lld",b+i),c[++c[0]]=b[i];
23     sort(a+1,a+n+1),sort(b+1,b+n+1);
24     for (i=1;i<=n;i++) c[++c[0]]=b[i]-l,c[++c[0]]=b[i]+l;
25 
26     sort(c+1,c+c[0]+1);
27     LL low,high,mid,ans;
28     low=0,high=l;
29     while (low<=high){
30         mid=(low+high)>>1;
31         if (feasible(mid)){
32             ans=mid;
33             high=mid-1;
34         }
35         else
36             low=mid+1;
37     }
38     printf("%lld",ans);
39     return 0;
40 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

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