答题思路

贪心练习题。如果有一只鸡可以在

T

时刻到达谷仓，也就是

x_{i}+ v_{i}\times T\ge B

，则记录它为可以经过的鸡。如果这只鸡前面有不能到达的鸡挡着他，那么对这些鸡全部操作一遍，以确保它可以到达终点。特别的，这一只鸡前面的另一只可以通过的鸡是不需要操作的，因为跟着前面那只鸡也可以到达终点。最后当已经有

k

只鸡经过终点，就可以输出了。对于代码实现，由于需要看这只鸡前面的无法通过的鸡的数量，所以需要倒序枚举。

代码展示

CPP

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

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

文章操作

答题思路

代码展示

相关推荐

评论

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