题目来源
链接：https://ac.nowcoder.com/acm/contest/11229/D
来源：牛客网
题目描述
牛牛参加了牛妹的派对。
牛牛面前有一个圆桌，圆桌边缘按顺序摆上了 n 个蛋糕（第一个蛋糕和第 n个蛋糕相邻）。
每个蛋糕都有一个饱腹值和奶油含量。
牛牛不喜欢吃奶油，所以他想要在保证自己能吃饱（所吃蛋糕的饱腹度的和大于等于 sss）的情况下，所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。我们知道，牛牛一直都是个绅士。所以他选择的蛋糕应该是相邻的（也就是对应圆上的一段弧（也可以是整个圆））。
现在它想请你帮它计算在能够吃饱的情况下，他吃到蛋糕中奶油含量最高的那一个最低会是多少？
输入描述:
1
2
3
4
5
6
| 输入共三行。
第一行两个正整数 n,s 。
接下来的一行 n 个整数 a1...a代表第一个到第 n 个蛋糕每个蛋糕的饱腹值。
接下来的一行 n个整数 b1...bn 代表第一个到第 n 个蛋糕每个蛋糕的奶油含量。
保证：1≤n≤2×105; 1≤s≤109; 1≤ai,bi≤109 (1≤i≤n);
|
输出描述:
1
2
| 输出共一行代表答案。
特别的，若牛牛吃掉所有蛋糕都无法吃饱
|
输入
输出
说明
1
2
3
4
5
6
| 选择第 1，2，4，5 个蛋糕：
饱腹值：4+3+6+1=14>9
最大奶油含量：max{1,3,2,5}=5
所以输出 5。
|
算法解析
本题使用算法为，环形问题 + 双指针
环形问题
因为牛牛是只吃旁边的蛋糕，而且蛋糕排列呈现环形，我们可以定义大小为 2*n 的数组来进行环形处理。这样无论牛牛从那个蛋糕开始吃，我们都能让这个蛋糕数组的后面有其它所有蛋糕的数据。
双指针
分析题目可知，我们要在吃的饱的情况下，找到他吃到蛋糕中奶油含量最高的那一个最低（若不理解可以看题目说明）会是多少？
每个蛋糕的最大奶油含量为1<=b<=10^9,那我们只要在这个范围内进行双指针判定就可以拉，通过双指针定位可以以满足条件的奶油含量。
笔者代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| import java.util.HashSet;
import java.util.Scanner;
public class Main {
static int[] arr ;
static int[] v ;
static int s,n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
s = scanner.nextInt();
long sum = 0 ;
arr = new int [n*2+1];
v = new int [n*2+1];
for(int i = 0;i<n;i++){
arr[i] = scanner.nextInt();
arr[i+n] = arr[i];
sum +=arr[i];
}
for(int i =0;i<n;i++){
v[i] = scanner.nextInt();
v[i+n] = v[i];
}
if(sum<s){
System.out.println("-1");
return;
}
int l = 1,r = (int) (1e9+10);
while(l<r){
int mid = (l+r)>>1;
if(check(mid)){
r =mid;
}else {
l = mid+1;
}
}
System.out.println(l);
}
public static boolean check(int ans){
long eatcake = 0;
for(int i = 0;i<2*n;i++){
if(v[i]>ans){
eatcake = 0;
}else {
eatcake+=arr[i];
if(eatcake>=s){
return true;
}
}
}
return false;
}
}
|
