pypy3 解法, 执行用时: 1671ms, 内存消耗: 94820K, 提交时间: 2022-06-18 21:33:36
n,s=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
if sum(x)<s:
print(-1)
exit(0)
my = max(y)
mx = y.index(my)
x = x[mx+1:]+x[:mx]
if sum(x)<s:
print(my)
exit(0)
def dfs(x,y):
if(len(set(y))==1 or len(set(x))==1):return y[0]
ps = y.index(max(y))
x1=x[:ps]
x2=x[ps+1:]
s1,s2=sum(x1),sum(x2)
if s1 < s and s2<s:
return y[ps]
if s1>=s:
ans1=dfs(x1,y[:ps])
else: ans1=1000000000
if s2>=s:
ans2=dfs(x2,y[ps+1:])
else: ans2=1000000000
return min(ans1,ans2)
print(dfs(x,y[mx+1:]+y[:mx]))
Python3 解法, 执行用时: 1203ms, 内存消耗: 55020K, 提交时间: 2022-06-19 21:06:00
def dfs(x,y):
if(len(set(y))==1 or len(set(x))==1):return y[0]
ps = y.index(max(y))
x1=x[:ps]
x2=x[ps+1:]
s1,s2=sum(x1),sum(x2)
if s1 < s and s2<s:
return y[ps]
if s1>=s:
ans1=dfs(x1,y[:ps])
else: ans1=0x7fffffff
if s2>=s:
ans2=dfs(x2,y[ps+1:])
else: ans2=0x7fffffff
return min(ans1,ans2)
n,s=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
if sum(x)<s:
print(-1)
exit(0)
my = max(y)
mx = y.index(my)
x = x[mx+1:]+x[:mx]
if sum(x)<s:
print(my)
exit(0)
print(dfs(x,y[mx+1:]+y[:mx]))
C++ 解法, 执行用时: 212ms, 内存消耗: 6684K, 提交时间: 2022-06-19 09:51:31
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+100;
ll n,s,sum;
ll a[N*2],b[N*2];
bool check(ll mid){//二分答案
ll ans=0;
for(int i=1;i<=n*2;i++){
if(b[i]<=mid){
ans+=a[i];
if(ans>=s)return 1;
}
else ans=0;
}
return 0;
}
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
sum+=a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
b[i+n]=b[i];
}
if(sum<s){
cout<<-1;
return 0;
}
ll l=1,r=1e9+10;
while(l<r){
ll mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
个蛋糕（第一个蛋糕和第 
）的情况下，所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。我们知道，牛牛一直都是个绅士。所以他选择的蛋糕应该是相邻的（也就是对应圆上的一段弧（也可以是整个圆））。。
代表第一个到第
代表第一个到第
