题目链接:https://atcoder.jp/contests/abc388/tasks/abc388_e
题意:
给定一个数组,当数组中一个数的两倍不超过另一个数时,认为这两个数可以组成一对,(组合后这两个数无法再次进行组合),求最大组合数
思路:
如果能条件能满足k对,一定能满足k-1对。同时尽量让 小的 和 大的里面相对小 的组合
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn=5e5+5;
ll arr[maxn];
ll ans;
bool check(int mid)
{
for(int i=1;i<=mid;i++)
{
if(2*arr[i]>arr[n-mid+i])return false;
}
return true;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>arr[i];
int l=0;
int r=n/2;
while(l<=r)
{
int mid= l+r>>1;
if(check(mid))
{
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<< ans;
return 0;
}
标签:arr,组合,int,ll,mid,Simultaneous,ans,Kagamimochi,贪心 From: https://www.cnblogs.com/benscode/p/18666793