当前位置:网站首页>E. Breaking the Wall
E. Breaking the Wall
2022-07-06 16:04:00 【It's Xiao Zhang, ZSY】
Original link
Monocarp plays “Rage of Empires II: Definitive Edition” — a strategic computer game. Right now he’s planning to attack his opponent in the game, but Monocarp’s forces cannot enter the opponent’s territory since the opponent has built a wall.
The wall consists of n sections, aligned in a row. The i-th section initially has durability ai. If durability of some section becomes 0 or less, this section is considered broken.
To attack the opponent, Monocarp needs to break at least two sections of the wall (any two sections: possibly adjacent, possibly not). To do this, he plans to use an onager — a special siege weapon. The onager can be used to shoot any section of the wall; the shot deals 2 damage to the target section and 1 damage to adjacent sections. In other words, if the onager shoots at the section x, then the durability of the section x decreases by 2, and the durability of the sections x−1 and x+1 (if they exist) decreases by 1 each.
Monocarp can shoot at any sections any number of times, he can even shoot at broken sections.
Monocarp wants to calculate the minimum number of onager shots needed to break at least two sections. Help him!
Input
The first line contains one integer n (2≤n≤2⋅105) — the number of sections.
The second line contains the sequence of integers a1,a2,…,an (1≤ai≤106), where ai is the initial durability of the i-th section.
Output
Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.
Examples
inputCopy
5
20 10 30 10 20
outputCopy
10
inputCopy
3
1 8 1
outputCopy
1
inputCopy
6
7 6 6 8 5 8
outputCopy
4
inputCopy
6
14 3 8 10 15 4
outputCopy
4
inputCopy
4
1 100 100 1
outputCopy
2
inputCopy
3
40 10 10
outputCopy
7
Note
In the first example, it is possible to break the 2-nd and the 4-th section in 10 shots, for example, by shooting the third section 10 times. After that, the durabilities become [20,0,10,0,20]. Another way of doing it is firing 5 shots at the 2-nd section, and another 5 shots at the 4-th section. After that, the durabilities become [15,0,20,0,15].
In the second example, it is enough to shoot the 2-nd section once. Then the 1-st and the 3-rd section will be broken.
In the third example, it is enough to shoot the 2-nd section twice (then the durabilities become [5,2,4,8,5,8]), and then shoot the 3-rd section twice (then the durabilities become [5,0,0,6,5,8]). So, four shots are enough to break the 2-nd and the 3-rd section
The idea is simple , It's a case by case discussion (3 In this case , See the code for details. ) Why can't I write it during the game? Woo woo
#include<bits/stdc++.h>
using namespace std;
int const N=2e5+10;
int a[N];
int res=1e9;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
// Break the adjacent
for(int i=1;i<n;i++)
{
res=min(res,max(max((a[i]+1)/2,(a[i+1]+1)/2),(a[i]+a[i+1]+2)/3));
}
// Break the left and right sides of the value
for(int i=2;i<n;i++)
{
res=min(res,min(a[i+1],a[i-1])+(abs(a[i-1]-a[i+1])+1)/2);
}
sort(a+1,a+1+n);
// Break the irrelevant ;
res=min(res,(a[1]+1)/2+(a[2]+1)/2);
cout<<res<<endl;
return 0;
}
边栏推荐
- China's salt water membrane market trend report, technological innovation and market forecast
- Matlab comprehensive exercise: application in signal and system
- 渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
- 0-1 knapsack problem (I)
- [exercise-2] (UVA 712) s-trees
- CS zero foundation introductory learning record
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- Opencv learning log 33 Gaussian mean filtering
- 信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
- Penetration test (4) -- detailed explanation of meterpreter command
猜你喜欢
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Information security - threat detection - detailed design of NAT log access threat detection platform
快速转 TypeScript 指南
Gartner: five suggestions on best practices for zero trust network access
[exercise-5] (UVA 839) not so mobile (balance)
信息安全-威胁检测引擎-常见规则引擎底座性能比较
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
X-Forwarded-For详解、如何获取到客户端IP
Penetration test (8) -- official document of burp Suite Pro
Record of force deduction and question brushing
随机推荐
B - 代码派对(女生赛)
Determine the Photo Position
Research Report of peripheral venous catheter (pivc) industry - market status analysis and development prospect prediction
Opencv learning log 19 skin grinding
[exercise -10] unread messages
[exercise-7] (UVA 10976) fractions again?! (fraction split)
Auto.js入门
Penetration test (1) -- necessary tools, navigation
frida hook so层、protobuf 数据解析
Information security - Analysis of security orchestration automation and response (soar) technology
Accounting regulations and professional ethics [5]
Frida hook so layer, protobuf data analysis
树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
Ball Dropping
0 - 1 problème de sac à dos (1)
1010 things that college students majoring in it must do before graduation
渗透测试 ( 4 ) --- Meterpreter 命令详解
HDU-6025-Coprime Sequence(女生赛)
Matlab comprehensive exercise: application in signal and system
China's earthwork equipment market trend report, technical dynamic innovation and market forecast