[202401C]巨人之力的题解

本文主要是介绍[202401C]巨人之力的题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题描述：

时间限制: 1000ms

空间限制: 262144kb

题目描述

两千多年以前，身为艾尔迪亚人的尤弥尔意外获得巨人之力，并且创造了九大巨人，其无以匹敌的力量使得整个世界都陷入了无尽的战乱纷争，艾尔迪亚之外的人类过着惨淡的生活，生灵涂炭。某天，艾尔迪亚的初代王厌倦了战争，战争的罪孽感使他奉行不战主义，于是他带着一部分艾尔迪亚人蜗居在帕拉迪岛上，并且篡改了这些子民的记忆，让他们忘记了自己能够变成巨人的事实，从此与世隔绝。

而世界不会忘记艾尔迪亚人的罪孽！其中马莱国掌控了艾尔迪亚残党，虽然这些残党也拥有巨人之力，但是他们从小就被灌输着马莱的历史文化思想，深知自己是祖先的余孽。并且科技是第一生产力，仅靠这些残党的力量无法抵御发展数百年的热兵器的攻击。

就在今天，马莱国将要实施复仇计划，准备入侵帕拉迪岛！小贝作为艾尔迪亚残党，也被马莱国用于攻击帕拉迪岛上的艾尔迪亚人。小贝的巨人之力可以使岛上的艾尔迪亚人化身巨人，从而“化敌为友”，帮助马莱国攻击帕拉迪岛。而实际上，小贝的内心深处不忍心岛上的同胞被巨人侵害得过于惨重，于是他向你求助，如何使得巨人力量总和最小。

帕拉迪岛上有 $n$ 名艾尔迪亚士兵站成一排抵御来自马莱国的攻击，其中第 $i$ 名士兵的力量值为 $a_i$ 。

小贝可以做若干轮以下操作：

选择两个位置 $l,r$ 满足 $1 \le l \le r \le n$ 。
$[l,r]$ 的士兵全部化身为巨人，且 $l < i <r$ 中的所有位置上的巨人的力量值变为 $\max(a_l,a_r)$ 。

$[l,r]$ 中有些位置上的士兵可能在之前的操作中已经变成巨人，但是在此轮这些巨人的力量也会得到改变。

你需要将所有士兵都变成巨人。若干轮操作之后，所有巨人的力量值总和最小是多少，即求 $\sum_{i=1}^na_i$ 的最小值。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数，表示 $n$ 名艾尔迪亚士兵的力量值。

输出格式

输出一个正整数，表示若干轮操作后，最小的巨人的力量值总和。

样例

Input 1

3
5 1 7

Output 1

Input 2

5
1 3 4 2 5

Output 2

Input 3 $i$

9
9 11 5 16 9 7 4 18 13

Output 3

数据范围

第 $1 \sim 10$ 个测试点： $1 \le n \le 100$
第 $11 \sim 20$ 个测试点： $1 \le n\le 10^5$
所有测试点： $1 \le a_i \le 10^9$

样例解释

样例中，选择区间顺序如下：
- $1 \sim 4$ ，序列变为 ${1,2,2,2,5}$ 。
- $5 \sim 5$ ，序列不变。

主要思路：

这题打爆力 $100\%$ 超时，我们可以这样子想：对于第 $i$ 个士兵，如果他的左边最小值和右边最小值比这个士兵要小，那么这个士兵一定会变成 $\max(l_i,r_i)$

否则，就还是原来的样子。

代码code：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int l[100010],r[100010];
int main()
{cin>>n;memset(l,0x3f,sizeof(l));memset(r,0x3f,sizeof(r));//别忘了初始化for(int i=1;i<=n;i++){cin>>a[i];l[i] = min(l[i-1],a[i]);}for(int i=n;i>=1;i--){r[i] = min(r[i+1],a[i]);}//预处理出l和rlong long ans=0;for(int i=1;i<=n;i++){if(a[i]>l[i]&&a[i]>r[i])//如果可以被改{ans+=max(l[i],r[i]);//改掉}else{ans+=a[i];//否则就不改}}cout<<ans;return 0;
}

这篇关于[202401C]巨人之力的题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！