codeforce每日一题
题目链接
题目分数:1700
题目描述
输入 $T(≤1e4)$ 表示 $T$ 组数据。所有数据的 $n$ 之和 $≤1e4$。
每组数据输入 $n(1≤n≤100)$ 和长为 $n$ 的严格递增数组 $k$,长为 $n$ 的数组 $h (1≤h[i]≤k[i]≤1e9)$。
你在玩一个打怪游戏。有 $n$ 只怪物,第 $i$ 只会在第 $k[i]$ 秒出现,血量为 $h[i]$。
你有一个引导类法术,你引导的时间越长,伤害越高,消耗的魔法值也越高。
具体来说,开始引导的第 $1$ 秒,伤害为 $1$,消耗 $1$;第 $2$ 秒,伤害为 $2$,消耗 $2$,依此类推。
你可以随时停止引导(停止后伤害为 $0$),或者重新引导(从 $1$ 开始)。
游戏从第 $1$ 秒开始。在第 $k[i]$ 秒,法术伤害至少要是 $h[i]$。
要击败所有怪物,至少要消耗多少魔法值
注:伤害达到 $2$,要消耗 $1+2=3$ 的魔法值;第 $i$ 秒,伤害为 $i$,消耗 $i$。
样例
输入样例1
3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2
输出样例1
10
6
7
算法
(贪心) $O(n)$
我们找出打败每一个怪兽所需的最短时间区间,就是$[Ki - Wi + 1, Ki]$,再找出哪些区间是有公共点的,有公共点的区间是需要连续的。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd emplace_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
cin>>n;
vector<PLL> w(n, {0, 0});
rep(i, 0, n - 1) cin>>w[i].se;
rep(i, 0, n - 1) cin>>w[i].fi, w[i].fi = w[i].se - w[i].fi + 1;
LL l = w[n - 1].fi, r = w[n - 1].se;
LL res = 0;
per(i, 0, n - 1)
{
if(w[i].se < l)
{
res += (r - l + 2) * (r - l + 1) / 2;
r = w[i].se;
}
l = min(l, w[i].fi);
}
res += (r - l + 1 + 1) * (r - l + 1) / 2;
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}