破链成环-acwing第131场周赛-奶牛报数

5364. 奶牛报数 - AcWing题库

有 n 头奶牛，围成一圈，顺时针依次编号为 1∼n。

其中，第 i 头奶牛的重量为 ai。

现在，我们需要选择一头奶牛，并从该奶牛开始，所有奶牛按照顺时针的顺序进行 1∼n报数。

报数完毕后，所有报出的数在 [l,r) 范围内的奶牛，会被选中制作牛肉。

我们希望：

1. 制作的牛肉尽可能多，即选中的奶牛的重量之和尽可能大。
2. 在满足上一条件的前提下，1 号奶牛报的数尽可能小。

请你找到满足上述条件的最佳报数方案，并输出该方案下，11 号奶牛报的数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含两个整数 l,r。

输出格式

一个整数，表示 11 号奶牛报的数。

数据范围

前 33 个测试点满足 2≤n≤5。
所有测试点满足 2≤n≤105，1≤ai≤104，1≤l<r≤n。

输入样例1：

3
1 2 3
1 3

输出样例1：

3

输入样例2：

5
1 2 3 4 1
1 3

输出样例2：

4

首先将原串复制一份拼接到后面，则任意一种报数方案都对应新串上一段长度为 n的区间

然后就是要找到最大最大的区间和，然后反推出1号奶牛报的点数

遍历数组的时候，通过前缀和快速得到区间和，反推1号奶牛报的数，可通过解方程，i-1 为当前区间右端点的位置，r 为当前区间右端点报的数，1号奶牛的位置为1，则可列出方程 1 - y = i - 1 - r , 得 y = r - i ，

就可以每次维护 y ，然后区间值更大时通过y更新答案。

AC code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, arr[200010];
ll s[200010];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i + n] = arr[i];
	}
	for (int i = 1; i <= n * 2; i++) {
		s[i] = s[i - 1] + arr[i];
	}

	int l = 0, r = 0;
	cin >> l >> r;
	int len = r - l;
	ll ans = LLONG_MIN;
	int in = 1;
	int num = 0;
	for (int i = len ; i <= 2 * n ; i++) {
		ll  res = s[i] - s[i - len];
		int y = r - i;
		while (y < 1) y += n;
		if (res > ans || res == ans && y < num) {
			ans = res;
//			in = i - len ;  in为最大区间左端点 
			num = y;
		}
	}
	cout << num;
}

 我最开始的思路是找到最大区间的左端点 in，然后反推 1 号奶牛的报数，但卡了一下午，没想出来，希望有大佬给出思路改正