题解：P13394 [GCJ 2010 #1B] Picking Up Chicks

· · 题解

题目传送门。

怎么 GCJ 的题满分和时间限制都这么奇葩。

思路

一道比较水的贪心题，本蒟蒻没看题解（似乎当时还没题解）就过了。

我们先从问题出发，题目问的是最小交换次数而不是最快速度之类的，所以我们可以将小鸡分成两类，第 1 类是可以在不考虑前方小鸡挡道的情况下能在不晚于时间 T 到达谷仓，第 2 类不行。分完类以后就不用考虑其他元素了。

如果我们想让离谷仓第 i 近的小鸡能在不晚于时间 T 到达谷仓（前提是它属于第 1 类），那么离谷仓第 1 \sim i-1 近的小鸡中第 2 类小鸡有多少只，就需要给它交换多少次。因为跟在第 2 类小鸡后面到不了谷仓，必须交换，而跟在第 1 类小鸡后面可以到达谷仓，无需交换。

那么很显然，离谷仓越近，前方的第 2 类小鸡就越少，交换次数也越少，所以我们只需要让前 K 只第 1 类小鸡到达谷仓即可，答案计算交换次数总和；如果第 1 类小鸡不足 K 只，答案就是IMPOSSIBLE。

代码实现

记得特判 K=0 的情况，直接输出 0。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,Case,n,k,b,t;
int x[60],v[60];
void print(int x)
{
    printf("Case #%lld: %lld\n",Case,x);
    return ;
}
signed main()
{
    cin>>T;
    for(Case=1;Case<=T;Case++)
    {
        cin>>n>>k>>b>>t;
        for(int i=1;i<=n;i++) cin>>x[i];
        for(int i=1;i<=n;i++) cin>>v[i];
        if(k==0)//特判 k=0 输出 0
        {
            print(0LL);
            continue;
        }
        int flag=0,ans=0,cnt=0,chick=0;
        for(int i=n;i;i--)
        {
            if(1.0*(b-x[i])/v[i]<=t)//第 1 类小鸡
            {
                ans+=cnt;
                chick++;
                if(chick>=k)
                {
                    flag=1;
                    print(ans);
                    break;
                }
            }
            else//第 2 类小鸡
            {
                cnt++;
            }
        }
        if(!flag) printf("Case #%lld: IMPOSSIBLE\n",Case);//IMPOSSIBLE
    }
    return 0;
}