Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
int n, ans = INT_MAX , k,s[N];
main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
for (int i=1 ;i <=n;i++){
cin>>s[i];
s[i]+= s[i-1];
}
if (s[n] < k){
cout<<-1;
return 0 ;
}
for (int i=1;i<=n;i++){
if (s[n] - s[i-1]>=k){
int u=lower_bound(s + i,s + 1 + n, k+s[i-1]) - s;
if (s[u]+s[i-1]>=k) ans=min(ans,u-i+1);
}
else{
int u=lower_bound(s+1,s + 1 + i , k - s[n] + s[i-1]) - s;
if (n-i+1+u<=n) ans=min(ans,n-i+u+1);
}
}
cout<<ans<<" ";
return 0;
//Thanhkhangdzn01
}
Hãy giúp mọi người biết câu trả lời này thế nào?
`\color{red}{\text{@hoangduy67}}`
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,a[1000005],SUM[1000005]={0},i,VT,res=1e9,k,sum[1000005]={0},vt;
ll SOLVE ( ll l ){
ll r=n,mid,res=0;
while ( l<=r ){
mid = (l+r)/2;
if ( SUM[mid]+sum[i]>=k ){
res = mid;
l = mid + 1 ;
}
else r = mid - 1;
}
return res;
}
ll solve ( ll r ){
ll l=0,mid,res=0;
while ( l<=r ){
mid = (l+r)/2;
if ( sum[i]-sum[mid]>=k ){
res = mid;
l = mid + 1 ;
}
else r = mid - 1;
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for ( i=1;i<=n;i++ ){
cin >> a[i];
sum[i] = sum[i-1]+a[i];
}
if ( sum[n]<k ){
cout << -1;
return 0;
}
for ( i=n;i>=1;i-- ) SUM[i] = SUM[i+1] + a[i];
for ( i=1;i<=n;i++ ){
if ( sum[i]>=k ){
vt = solve ( i-1 );
if ( vt==0 ) res = min ( res, i );
else res = min ( res,i-vt );
}
else {
VT = SOLVE (i+1);
res = min ( res , i+n-VT+1 );
}
}
cout << res ;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin
15
280
2
if (s[n] - s[i-1]>=k){ int u=lower_bound(s + i,s + 1 + n, k+s[i-1]) - s; if (s[u]+s[i-1]>=k) ans=min(ans,u-i+1); } else{ int u=lower_bound(s+1,s + 1 + i , k - s[n] + s[i-1]) - s; if (n-i+1+u<=n) ans=min(ans,n-i+u+1); } cái if là để tìm đoạn con sao cho nó lớn hơn k á còn cái else là vì cái k có đoạn con nào từ vị trí i đến n thỏa k nên sẽ tìm cái đoạn con sao cho s[n] + s[i] > k với i<n Rút gọnif (s[n] - s[i-1]>=k){ int u=lower_bound(s + i,s + 1 + n, k+s[i-1]) - s; if (s[u]+s[i-1]>=k) ans=min(ans,u-i+1); } else{ int u=lower_bound(s+1,s + 1 + i , k - s[n] + s[i-1]) ... xem thêm