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

贪心。

显然优先守卫

k_i

更大的防御段，这样单个士兵的贡献更高。

但是该段最后可能剩下不到

k_i

个敌人，此时最后一个个士兵的贡献会减少。

于是我们使用 map 统计贡献为

x

的士兵数量

y

，优先选贡献更大的士兵。

在一个防御段中，前

\big \lfloor \frac{a_i}{k_i} \big \rfloor

个士兵的贡献为

k_i

，最后一个士兵的贡献为

a_i \bmod k_i

。

按贡献排序后，用敌人总个数减去消灭掉的敌人个数即可。

参考代码：

CPP

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define PLL pair<ll, ll>

const int N = 300050;

int n, s, a, k;
ll ans;
map<ll, ll> mp;
vector<PLL> cnt;

bool cmp(PLL a, PLL b){
	return a.first > b.first;
}

int main() {
	cin >> n >> s;
	for(int i = 1; i <= n; i ++){
		cin >> a >> k;
		ans += a;
		mp[k] += a / k;
		mp[a % k] ++;
	}
	for(PLL i : mp)
		cnt.push_back(i);
	sort(cnt.begin(), cnt.end(), cmp);
	for(PLL i : cnt){
		if(i.second < s){
			s -= i.second;
			ans -= i.first * i.second;
		}
		else{
			ans -= s * i.first;
			break;
		}
	}
	cout << ans;
	return 0;
}

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

文章操作

参考代码：

相关推荐

评论

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