训练地址:vjudge链接
D.Friends and the Restaurant
首先考虑的\(b_i-a_i\)就不说了,然后就是考虑给了一堆整数,怎么组合出最多的成组的二数以上的组。其实就是充分的利用元素中的负数。可以看到,利用两个正数带一个负数是亏本的,所以想要得到想要的结果,必定是正+正或者正+负$\geq$0。为了取到最大,我们可以从最大数递减的角度入手,找到数组中第一个也就是最小的数,使得两者和满足 $\geq$0,以此来遍历找全。
下见代码:
//>>>Qiansui
#include<map>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
using namespace std;
const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],b[maxm],cnt,ans;
void solve(){
cnt=0;
cin>>n;
vector<int> vis(n+5,0);
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<n;++i){
cin>>b[i];
b[i]-=a[i];
}
sort(b,b+n);
cnt=0;
for(int i=n-1,j=0;i>=0;--i){
while(j<i&&b[i]+b[j]<0) ++j;
if(i<=j) break;
else{
++cnt;
++j;
}
}
cout<<cnt<<"\n";
return ;
}
signed main(){
// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--){
solve();
}
return 0;
}
标签:ch,训练,int,long,while,2023,include,define
From: https://www.cnblogs.com/Qiansui/p/17185727.html