题解：P14205 [ROI 2016 Day1] 要塞防御

题号：P14205

题目链接：P14205 [ROI 2016 Day1] 要塞防御

题目简述：

题目一共给我们

n

个防御段，每个防御段一名士兵可以抵御的敌人数量

k_i

和每个防御段会有的敌人数量

a_i

以及我们的士兵总量

s

。要我们通过合理分配士兵，求出最少会有多少名敌人突破防线。

思路：

这道题很显然，我们优先选择让士兵去

k_i

更大的防御段是最优解，因为这时一名士兵所能抵御的敌人数量就更多一些。可这时，还有一个问题：

假如我们有一个会有

3

名敌人进攻的防御段，这个防御段一名士兵可以抵御

2

名敌人。那么，我们派一个人去这个防御段，这个士兵可以抵御

2

名敌人，可如果我们再派一个人去，就只能再让他抵御剩下的

1

名敌人了。

这个问题启发我们要处理最后

1

名士兵所能解决的敌人数量不是

k_i

的情况。

我们选择用 map 来记录一名士兵可以抵御的敌人数量，再从大到小选取。最后让敌人总数减去我们抵御住的敌人总数就可以了。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	x=0;char c;int sign=1;
	do{c=getchar();if(c=='-') sign=-1;} while(!isdigit(c));
	do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
	x*=sign;
}//快读增加输入效率
long long n,s;
long long a[100005],k[100005];
long long d[200005],l;
map<long long,long long> f;
bool cmp(long long s1,long long s2){
	return s1>s2;
}//从大到小排序
long long z;
int main(){
	read(n),read(s);
	for(int i=1;i<=n;i++){
		read(a[i]),read(k[i]);
		z+=a[i];//计算敌人总数
		d[++l]=k[i],d[++l]=a[i]%k[i];
		f[k[i]]+=a[i]/k[i];//记录一名士兵可以抵御k_i名敌人的数量
		f[a[i]%k[i]]++;//记录一名士兵可以抵御a_i % k_i名敌人的数量
	}
	sort(d+1,d+l+1,cmp);//贪心排序
	for(int i=1;i<=l;i++){
		if(d[i]==d[i-1]) continue;//避免重复选择
		if(f[d[i]]<=s) z-=f[d[i]]*d[i],s-=f[d[i]];//计算答案
		else z-=d[i]*s,s=0;//计算答案
	}
	cout<<z;//输出答案
	return 0;
}

总结：

本题利用贪心思想，总体难度不算太高，适合用作贪心初学者的练习题。

题解：P14205 [ROI 2016 Day1] 要塞防御

文章操作

题号：P14205

题目链接：P14205 [ROI 2016 Day1] 要塞防御

题目简述：

思路：

代码：

总结：

相关推荐

评论

题解：P14205 [ROI 2016 Day1] 要塞防御