Educational Codeforces Round 121 (Rated for Div. 2) C. Monsters And Spells 数学

题目链接：Problem - C - Codeforces

题目描述：

输入描述： 

输出描述：

样例及解释：

 题意：t组样例，然后是n只怪兽第一行是每只怪兽出现的时间，下面一行是怪兽的血量，你可以使用x法力值造成x的伤害（连续释放同时+1）,问最小需要多少法力值

思路：无限高斯求和即可，我们可以通过时间和血量算出杀死这只怪兽需要在第几秒开始蓄力，然后根据这个进行排序。在根据下一次蓄力的时间和这次结束的时间来判断是一直累加还是从头开始

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
	ll h;
	ll k;
	ll a;
}arr[105];
bool cmp(node a, node b){
	return a.a < b.a;
}
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	int n;
	while(t--){
		cin >> n;
		ll sum = 0;
		for(int i = 0; i < n; i++){
			cin >> arr[i].k;
		}
		for(int i = 0; i < n; i++){
			cin >> arr[i].h;
			arr[i].a = arr[i].k - arr[i].h + 1;
		}
		sort(arr, arr + n, cmp);
		ll ans = 0;
		sum = (arr[0].h + 1) * arr[0].h / 2;
		ll cnt = arr[0].k;
		ans = arr[0].h;
		for(int i = 1; i < n; i++){
			if(arr[i].k <= cnt){
				continue;
			}else{
				if(arr[i].a > cnt){
					sum += (arr[i].h + 1) * arr[i].h / 2;
					ans = arr[i].h;
					cnt = arr[i].k;
				}else{
					cnt++;
					ans++;
					ll ans1 = ans + arr[i].k - cnt;
					sum += (ans + ans1) * (ans1 - ans + 1) / 2;
					cnt = arr[i].k;
					ans = ans1;
				}
			}
		}
		cout << sum << endl;
	}
	return 0;
}

最后

以上就是辛勤外套为你收集整理的Educational Codeforces Round 121 (Rated for Div. 2) C. Monsters And Spells 数学的全部内容，希望文章能够帮你解决Educational Codeforces Round 121 (Rated for Div. 2) C. Monsters And Spells 数学所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。