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

· · 题解

答题思路

贪心练习题。如果有一只鸡可以在 T 时刻到达谷仓，也就是 x_{i}+ v_{i}\times T\ge B ，则记录它为可以经过的鸡。如果这只鸡前面有不能到达的鸡挡着他，那么对这些鸡全部操作一遍，以确保它可以到达终点。特别的，这一只鸡前面的另一只可以通过的鸡是不需要操作的，因为跟着前面那只鸡也可以到达终点。最后当已经有 k 只鸡经过终点，就可以输出了。对于代码实现，由于需要看这只鸡前面的无法通过的鸡的数量，所以需要倒序枚举。

代码展示

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c,x[100];
int v[100];
bool bl[100];
signed main()
{
    cin>>c;
    for(int T=1;T<=c;T++)
    {
        int n,k,b,t
        int tmp=0,sum=0,ans=0;
        //分别表示 
        //不可能走到谷仓的鸡的数量
        //已经有几只鸡到达了
        //答案统计 
        memset(bl,0,sizeof(bl));//多测清空
        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(x[i]+v[i]*t>=b) bl[i]=1;//打标记 
        }
        for(int i=n;i>=1;i--)
        {
            if(sum>=k) break;//当已经有k只鸡通过，直接跳出循环 
            if(bl[i]) ans+=tmp,sum++;//如果被标记，前面不可能走到谷仓的鸡全部操作一遍 
            else tmp++;//没被标记，计数 
        }
        cout<<"Case #"<<T<<": ";
        if(sum<k) cout<<"IMPOSSIBLE"<<endl;//无解 
        else cout<<ans<<endl;
    }
    return 0;
}