打卡信奥刷题（3601）用C++实现信奥题 P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2

P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2

题目背景

译自 第24回日本情報オリンピック 本選 T2。

题目描述

比太郎要打怪。

令比太郎初始时的力量为 $x$。有 $N$ 个怪物，编号 $1\sim N$。欲打败第 $i$（$1\le i\le N$）个怪物，需要力量 $\ge A_i$。打败第 $i$（$1\le i\le N$）个怪物，会使比太郎的力量增加 $B_i$。

比太郎会用如下的策略打怪：

• 选择整数 $j$（$1\le j\le N$），然后按 $j,j+1,\cdots ,N$ 的顺序打怪。
• 如果 $j\ge 2$，回头按顺序打怪物 $1,2,\cdots ,j-1$。

在按照策略打完所有的怪物的前提下，求出比太郎初始力量 $x$ 的最小值。

输入格式

如下所示：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

输出格式

输出一行一个整数，即比太郎初始力量 $x$ 的最小值。

输入输出样例 #1

输入 #1

5
1 3 2 8 6
4 3 1 1 2

输出 #1

1

输入输出样例 #2

输入 #2

5
1 6 3 3 2
1 2 1 0 1

输出 #2

3

输入输出样例 #3

输入 #3

10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1

输出 #3

9

输入输出样例 #4

输入 #4

7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580

输出 #4

0

说明/提示

样例解释

样例 $1$ 解释

令 $x=1$，然后按照 $1\to 5$ 的顺序打怪。

该样例满足子任务 $1,2,3,5$ 的限制。

样例 $2$ 解释

令 $x=3$，然后先打 $3\to 5$ 的怪，再打 $1\to 2$ 的怪。

该样例满足子任务 $1,2,3,5$ 的限制。

样例 $3$ 解释

该样例满足所有子任务的限制。

样例 $4$ 解释

该样例满足子任务 $1,2,3,5$ 的限制。

数据范围

• $2\le N\le 5\times 10^5$。
• $0\le A_i\le 10^9$（$1\le i\le N$）。
• $0\le B_i\le 10^9$（$1\le i\le N$）。
• 输入的值全部是整数。

子任务

1. （10pts）$N\le 2,000$，保证答案不大于 $10$。
2. （21pts）$N\le 2,000$。
3. （19pts）保证答案不大于 $10$。
4. （22pts）$B_i=1$（$1\le i\le N$）；
5. （28pts）无额外限制。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e5+10,MAXLL=4611686018427387903;
ll n,a[2*MAXN],b[2*MAXN],sum[2*MAXN],w[2*MAXN],q[2*MAXN],ans=MAXLL;
int main() {
	scanf("%lld",&n);
	for(int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		a[i+n]=a[i];
	}
	for(int i=1; i<=n; i++) {
		scanf("%lld",&b[i]);
		b[i+n]=b[i];
	}
	for(int i=1; i<=2*n-1; i++) {
		sum[i]=sum[i-1]+b[i];
		w[i]=a[i]-sum[i-1];
	}
	int head=1,tail=0;
	for(int i=1; i<=n-1; i++) {
		while(w[q[tail]]<=w[i]&&head<=tail) 
			tail--;
		q[++tail]=i;
	}
	for(int i=n; i<=2*n-1; i++) {
		while(q[head]<i-n+1&&head<=tail) 
			head++;
		while(w[q[tail]]<=w[i]&&head<=tail) 
			tail--;
		q[++tail]=i;
		ans=min(ans,w[q[head]]+sum[i-n]);
	}
	printf("%lld",ans);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/rogeliu/article/details/166883257