C. Circle of Monsters

Circle of Monsters"/>

C. Circle of Monsters

感觉有必要记录一下这道思维题

题目意思是这样的，给你若干个怪兽，并给出他们的生命值和爆炸所造成的伤害，现在他们围成一个环，怪兽如果被打死了，他将会带给下一个位置的怪兽相应爆炸伤害，如果下一个位置没有怪兽，则无效，每开一枪减少怪兽一点生命值，现在问最少要开几枪能够杀死所有怪兽

• 我想会不会是把所有怪兽放进一个小顶堆里面，每次弹出生命值最小的怪兽？这样不对，很容易能够找到反例
• 如何做呢？现在的问题是不知道从谁开始杀，也就是说第一个怪兽我们一定是要杀死的，这样它带来的爆炸才能够开始起作用，杀谁呢？不知道，那就一个一个看，所以我们需要维护一下每个怪兽至少需要开多少枪，也就是前一个怪兽爆炸能够带来多少影响，这样我们得到这个总和，再枚举杀每一个怪兽的情况，取最小值就得到了最终答案

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <iomanip>
#include <unordered_map>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
ll a[MAXN], b[MAXN];
ll c[MAXN];
int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t, n;cin >> t;while(t--){cin >> n;for(int i=0;i<n;i++){cin >> a[i] >> b[i];}ll num = 0;for(int i=0;i<n;i++){c[i] = max(0ll, a[i] - b[(i - 1 + n) % n]);num += c[i];}ll ans = __LONG_LONG_MAX__;for(int i=0;i<n;i++){ans = min(ans, a[i] + num - c[i]);}cout << ans << '\n';}return 0;
}