[CF373C]计算袋鼠是愉快的(Counting Kangaroos is Fun)-贪心

Problem 计算袋鼠是愉快的

题目大意

有n只袋鼠，如果一个袋鼠体积是另一个袋鼠的两倍或以上，则小袋鼠能被大袋鼠装进袋子里，装进去后就看不到袋子里的袋鼠了，问这群袋鼠如何行动才能使得它们看着数量最少，请输出该数量。（注意，如果一个小袋鼠被装在袋子里，则小袋鼠袋子里不能再嵌套袋鼠了）

也就是给出一个数组，求这个数组中最多的u,v使得u>=2v,每个数组中的数只能作为一次u，v

（具体还是直接看题吧）

Solution

首先我们考虑最优情况，一定有：最小ans≥n/2，这是题目限制条件可得的。

所以，首先我们先将这个数组排序。

易得，大袋鼠取越大一定是越优的。所以最小ans情况下，我们的大袋鼠一定是取 值最大 的ans个数。

且我们通过排序性质可得，被装进袋子里的袋鼠一定是取位置≤n/2的数，因为这里的数一定比后面的要小，所以更优。

所以我们将这个数组切成两部分，以n/2为界限。枚举前半段，从n/2->1，若能放进目前最大可放的袋鼠就放进去。

这样所得的答案是最优答案，代码也超级短。贪心果然是好的。

AC Code

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int n,a[];

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     sort(a+,a+n+);

     int ans=n;

     for(int i=n>>;i>;i--)

         if(a[ans]>=(a[i]<<))ans--;

     printf("%d\n",ans);

 }