1334 - C. Circle of Monsters（贪心）

ゝ一纸荒年。 2021-07-16 15:07 274阅读 0赞

[题目][Link 1]

思路：当我们选定了一个怪物作为开始先杀掉后，对于余下的怪物我们一定要按顺序一个个杀掉，因为对于一开始被杀的后一个怪物（如果没炸死的话）我们最终一定要杀掉的，如果他是在他后面一个怪物被杀之后被杀那么它的爆炸不会产生贡献，我们在贪心的决断下，一定要先杀他让它的爆炸伤害物尽其用。那么其实我们只需枚举一下各个怪物第一个杀，取最小即可。但暴力的话复杂度O(n^2)，但可以发现其实对于每一个结果只是改动了一个小地方。我们先求出一个假设每个怪物的爆炸伤害都做出了贡献的sum=min（i-1的爆炸伤害-i的生命值，0)i=1,2,3…n 。然后枚举每一个i，ans=min(ans,sum+i怪物的生命-min（i-1的爆炸伤害-i的生命值，0))，因为第一个杀i怪的所需子弹数，与sum相比就是加一个先杀i怪的生命减一个min（i-1的爆炸伤害-i的生命值，0).

Code:

#include<iostream>
    #include<vector>
    #include<algorithm>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll a[Max], b[Max];
    
    int main()
    { 
    	FAST;int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		ll sum = 0, ans = 0;
    		for (int i = 1;i <= n;i++)	cin >> a[i] >> b[i];
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (i == 1)sum += max(ll(0), a[i] - b[n]);
    			else sum += max(ll(0), a[i] - b[i - 1]);
    		}
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (i == 1)ans = a[i] + sum - max(ll(0), a[i] - b[n]);
    			else ans = min(ans, a[i] + sum - max(ll(0), a[i] - b[i - 1]));
    		}
    		cout << ans << endl;
    	}
    }

[Link 1]: https://codeforces.ml/contest/1334/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读

相关 AIX 关闭Writesrv 1334端口

startsrc -s writesrv & netstat -an | grep 1334 \ netstat -an | grep 1334 tcp4 0 0 \

比眉伴天荒/ 2023年10月18日 19:19/ 0 赞/ 73 阅读

相关贪心-C - Canoe

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

落日映苍穹つ/ 2023年07月12日 08:45/ 0 赞/ 117 阅读

相关 C - Jumps on a Circle

题目大意一个环，从0开始到p-1，开始位于0的位置，第一次走1步，第二次走2步，第三次走3步… 问n步后走过了多少个不同的点？ ------------------

缺乏、安全感/ 2022年10月13日 15:58/ 0 赞/ 20 阅读

相关 502. IPO【贪心】【C++】

假设力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO

你的名字/ 2022年09月10日 13:23/ 0 赞/ 160 阅读

相关 C++ Circle类

写点基础的，回顾一下。 include<iostream> define pi 3.14 using namespace std;

蔚落/ 2022年08月01日 00:13/ 0 赞/ 177 阅读

相关 codeforces C. Bits 贪心

C. Bits time limit per test 1 second memory limit per test 256 megabytes input sta

偏执的太偏执、/ 2022年07月24日 09:16/ 0 赞/ 185 阅读

相关 ACdream 1072 Kill The Monster （dp）

题目链接： [ACdream 1072][] 题意：中文题面…. 题解： dp 题。设dp\[t\]\[u\]\[i\]\[j\] 表示在时间 t

分手后的思念是犯贱/ 2022年06月12日 05:40/ 0 赞/ 148 阅读

相关 POJ 1827 Bunch Of Monsters(贪心)

Background Jim is a brave explorer. One day, he set out for his next destination, a my

迷南。/ 2022年06月11日 09:09/ 0 赞/ 106 阅读

相关 1334 - C. Circle of Monsters（贪心）

[题目][Link 1] 思路：当我们选定了一个怪物作为开始先杀掉后，对于余下的怪物我们一定要按顺序一个个杀掉，因为对于一开始被杀的后一个怪物（如果没炸死的话）我们最终一

ゝ一纸荒年。/ 2021年07月16日 15:07/ 0 赞/ 275 阅读

相关 C. Diamond Miner (贪心)

[题目][Link 1] 思路：模拟几个数会发现让绝对值大的距离相匹配花费相对小,所以将所有钻石矿的绝对值和矿工的绝对值分别存入两个数组，排序，两者都按从小到大计算距离相

墨蓝/ 2021年07月16日 13:58/ 0 赞/ 340 阅读