C. Monsters And Spells（Educational Codeforces Round 121 (Rated for Div. 2)）（区间合并，贪心）

63 阅读 0 评论 42 点赞

我是靠谱客的博主精明楼房，最近开发中收集的这篇文章主要介绍C. Monsters And Spells（Educational Codeforces Round 121 (Rated for Div. 2)）（区间合并，贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接：https://codeforces.com/contest/1626/problem/C

题意

一个人用魔力打怪，怪在第 $t_i$ 秒以 $h_i$ 点血量出现，一个人必须在怪出来的一瞬间就消灭怪物。
他在前一秒如果没有释放过魔法，则本次魔法的伤害是 $1$ 点，否则，设上一秒的伤害为 $x$ ，则本次伤害可以为 $x + 1$ 或者 $1$ 。
魔法消耗的法力值和造成的伤害值相同。
问消灭怪物的最小魔法消耗。

思路

对于第 $t_i$ 秒出现的怪物，则最晚开始准备的时间为第 $t_i-h_i-1$ 秒，所以我们可以把每一个怪物这样处理出来，最后进行区间合并，每个单独的区间都是从 $1$ 开始的等差数列，用等差数列求和公式计算即可。

AC代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
typedef double db;
const int N=5e5+10;

vector<pair<LL,LL> > v;
LL k[N];
LL h[N];

int main()
{
    int t;
    scanf("%d",&t);
	while(t--)
	{
		LL ans=0;
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
		for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
		for(int i=1;i<=n;i++)
		{
			int x=k[i]-h[i]+1;
			v.pb({x,k[i]});
		}
		sort(v.begin(),v.end());
		for(int i=0;i<n;i++)
		{
			int j=i+1;
			LL r=v[i].se;
			while(j<n)
			{
				if(v[j].fi>r) break;
				r=max(r,v[j].se);
				j++;
			}
			j--;
			ans+=(2LL+r-v[i].fi)*(r-v[i].fi+1)/2;
			i=j;
		}
		printf("%lldn",ans);
		v.clear();
	}
	return 0;
}

PS：比赛的时候用了一坨硬贪心，也丢在这里做一下对比。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
typedef double db;
const int N=5e5+10;

LL k[N];
LL h[N];

int main()
{
    int t;
    scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
		for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
		k[0]=0,h[0]=0;
		LL last=0;
		LL ans=0;
		int now=1;
		while(now<=n)
		{
			int idx=now;
			for(int i=now+1;i<=n;i++)
			{
				if(k[i]-k[now]<=h[i]-h[now]) now=i;
			}
			if(k[now]-k[idx-1]>=h[now]) ans+=(h[now]+1)*h[now]/2,last=h[now];
			else ans+=(last+1+last+k[now]-k[idx-1])*(k[now]-k[idx-1])/2,last+=k[now]-k[idx-1];
			now++;
		}
		printf("%lldn",ans);
	}
	return 0;
}