CF C. Monsters And Spells 思维

思维"/>

CF C. Monsters And Spells 思维

连接：传送门
题目描述：
题意：每次攻击可以是上一一时刻的攻击的伤害+1或者1（可以对着空气攻击），消耗的魔法等于每次攻击的伤害，n个怪物，每个怪物在ki时刻出现，血量为hi，在ki时刻打出的攻击必须不小于怪物的血量，问最少需要消耗多少魔法才可以杀死所有怪物？
分析：首先我们得知道在ki时刻打出的攻击必须大于等于hi。那么我们就只需要在打败这一时刻的怪物时，要不要再连续攻击保证下一时刻的攻击仍不小于怪物的血量，还是从1开始也可满足下一时刻的攻击不小于怪物的血量。当然优先选择后一种方式。简单来讲就是将这n个怪物划分成几个区间，一个区间就代表一段连续攻击，然后求一个最小花费。具体可以看看代码。

#include<iostream>
#include<iostream>
#define IOS ios::sync_with_stdio(false);  
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<int, int> PII;struct cmp{bool operator() ( int a, int b){return a> b;    }
};
const int N=1e6+10;
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
int lowbit(int x){return x&-x;
}int T;
int n;
int ti[N],h[N];
int main(){cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)	cin>>ti[i];for(int i=1;i<=n;i++)	cin>>h[i];ll su=0;ll nu=0;//区间大小ll re=0;//需要攻击的次数for(int i=n;i;i--){	if(nu==0){//这个就是对最后一个进行一下特判nu=h[i];re=h[i];}else{re-=ti[i+1]-ti[i]; //需要攻击的次数和怪物之间的时间差比一下if(re<=0){//代表一个区间结束su+=(ll)(1+nu)*nu/2;nu=h[i];re=h[i];}	else{if(re<h[i])	nu+=h[i]-re,re=h[i];//代表攻击力小于怪物血量，需要扩一下区间。}	}}su+=(ll)(1+nu)*nu/2;//别忘了最后再加一下！！cout<<su<<"\n";}return 0;}