不难想到贪心

要求最后活着的鱼最少，那么对于每一条捕食者它所吃掉的鱼越大（或者说越接近自身体重的一半）肯定越优，比如10和6，它们都可以吃掉1,2,3，但4和5只能被10吃掉，那么显然我们让10去抢1,2,3是不如4和5，所以我们考虑排序，再从大往小吃。

需要注意的地方

• 看这样一组数据：
• 8
• 1 1 1 1 114 514 114514 514114
• 如果L从最大开始的话会出现514114吃514,114514吃114的情况，但显然不是最优的，所以注意L的初始值

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int N=5e6+5;
const int Si=5e6+10;
int n;
int a[N];
int vis[N]; 
int l,r; //r是捕食者，l是被捕食者
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		vis[i]=1;//活着
	}
	sort(a+1,a+n+1);
	int ans=0;
	int flag=0;
	l=n/2;//没有初始值就消愁了
	for(r=n;r>=n/2;r--){
		flag=0;
		if(l==0)break;
		while(1){
			if(a[l]*2<=a[r]){
				flag=1;
				break;
			}
			l--;
			if(l==0){
				flag=-1;
				break;
			}
		}
		if(flag==-1)break;//及时结束
		else if(flag&&vis[r]/*如果被吃了那就吃不了别人了*/){
			vis[l]=0;
			l--;
			if(l==0)break;
		}
	}
	for(int i=1;i<=n;i++)ans+=vis[i];
	write(ans);
	return 0;
}

首先阅读题意，不难发现答案数不会超过 $\frac{n+1}{2}$ 个

所以我们可以进行贪心

先排序，贪心的方式就是对于前 $\frac{n}{2}$ 个小的枚举是否可以被吃掉，并且用更大的鱼去吃能被吃的较大的鱼

可以运用两个指针来枚举

时间复杂度 $O(\frac{n}{2})$ （应该是我也不确定）

一个错误的思路是排序过后从大往小枚举每一个数前面第一个可以被吃的数

提供一个样例

8
1 2 2 3 4 5 9 10
ans:4

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=5*1e6+10;
int n,ans=0;
int a[N];
bool vis[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
signed main(){
	ans=n=reads();
	for(int i=1;i<=n;i++) a[i]=reads();
	sort(a+1,a+n+1);
	int now=n/2;
	for(int i=n;i>=n/2+1;i--){
		if(vis[i]) continue;
		while(a[now]*2>a[i]||vis[now]) now--;
		if(!now) break;
		else{
			ans--;
			vis[now]=1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

大鱼吃小鱼 题解

题意简述

只有一条鱼的体重至少是另一条鱼的两倍时，体重更重的鱼才能吃掉另一条。n条鱼每两条一组，怎么分组才能使得最后活着的鱼的总数最少？输出最后活着的鱼的数量。

分析

考试时看了看数据范围，遂用二分 (请问我还会别的吗)，然后结合贪心。

先把这群鱼从小到大排序，然后把“活着的鱼的总数最少”变成“吃掉的鱼最多”这个问题，输出(n-吃掉的鱼)即可。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+7;
int n,l,r,ans,a[N];
int check(int x){
	int t=n;
	for(int i = x;i>=1;i--)
		if(a[t--]<2*a[i])return 0;
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	l=1,r=n>>1;
	for(int i = 1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	while(l<=r){
		int mid=(l+r+1)>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	ans=n-r;
	cout<<ans<<'\n';
	return 0;
} 

补充

• 最多只能有一半的鱼被吃掉。
• “找到的第一个能吃掉这条小鱼的大鱼就吃掉小鱼”这个做法（排序后）真的是正确的吗？
• 是正确的。不妨设更大的大鱼为m，若是m吃掉的这条小鱼，那么比这条小鱼大一丢丢的且能被m吃掉的那条“中小鱼”就无法被吃了（注意是一对鱼放到一个缸里！不能重复吃的！）。所以这个贪心没问题。
• 不可能越过这条小鱼，去找下一条“中小鱼”。