题解：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

。

CPP

#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;
}

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

文章操作

思路

代码实现

相关推荐

评论

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