#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w,a[100005],ans = -1,maxx=-1,minn = INT_MAX;
int d[100005];
void dif(){for (int i = 1;i <= n;i++) d[i] = a[i]-a[i-1];}
bool check(int x){
int cost = 0,cur = 0;
for (int i = 1;i <= n;i++){
cur += d[i];
if (cur<x){
int c = x-cur;
cost += c;
d[i] += c;
if (i+w<=n) d[i+w] -= c;
cur += c;
}
}
return cost <= m;
}
void solve(){/////////////////////
int l = minn,r = maxx+m,mid;
while (l<=r){
mid=(l+r)/2;
if (!check(mid)) r=mid-1;
else l=mid+1,ans=max(ans,mid);
dif();
}
}
signed main(){
int n,m,w;
cin >> n >> m>> w;
for (int i = 1;i <= n;i++){
cin >> a[i];
maxx = max(maxx,a[i]);
minn = min(minn,a[i]);
}
dif();solve();//////////////////////
cout << ans;
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w,a[100005],ans = -1,maxx=-1,minn = INT_MAX;
int d[100005];
void dif(){for (int i = 1;i <= n;i++) d[i] = a[i]-a[i-1];}
bool check(int x){
int cost = 0,cur = 0;
for (int i = 1;i <= n;i++){
cur += d[i];
if (cur<x){
int c = x-cur;
cost += c;
d[i] += c;
if (i+w<=n) d[i+w] -= c;
cur += c;
}
}
return cost <= m;
}
void solve(){
int l = minn,r = maxx+m,mid;
while (l<=r){
mid=(l+r)/2;
if (!check(mid)) r=mid-1;
else l=mid+1,ans=max(ans,mid);
dif();
}
}
signed main(){
int n,m,w;
cin >> n >> m>> w;
for (int i = 1;i <= n;i++){
cin >> a[i];
maxx = max(maxx,a[i]);
minn = min(minn,a[i]);
}
dif();///////////////////////////////
int l = minn,r = maxx+m,mid;
while (l<=r){
mid=(l+r)/2;
if (!check(mid)) r=mid-1;
else l=mid+1,ans=max(ans,mid);
dif();
}
cout << ans;
return 0;
}
当数据
IN:
2 5 1 5 8
OUT1:
8
OUT2:
13
为什么两段代码,一个调用函数,一个直接操作,输出反而不同?