【1044】Shopping in Mars (25 分)
  EIlYVvTMMLN7 2023年11月02日 39 0


#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
//key:Sum[j]-Sum[i-1]==S

const int N=100010;
int sum[N];
int n,S,nearS=100000010;

//upper_bound函数返回在[L,R)内第一个大于x的位置
int upper_bound(int L,int R,int x){
int left=L,right=R,mid;
while(left < right){
mid=(left+right)/2;
if(sum[mid] >x){
right=mid;
}else{
left=mid+1;
}
}
return left;
}

int main(){
scanf("%d%d",&n,&S); //元素个数,和值S
sum[0]=0; //初始化sum[0]=0
for(int i=1;i<=n;i++){
scanf("%d",&sum[i]);
sum[i] += sum[i-1]; //求sum[i]
}
for(int i=1;i<=n;i++){ //枚举左端点
int j=upper_bound(i,n+1,sum[i-1]+S); //求右端点
if(sum[j-1]-sum[i-1] == S){ //查找成功(注意是j-1而不是j)
nearS=S; //最接近S的值就是S
break;
}else if(j<=n && sum[j]-sum[i-1] <nearS){
//存在大于S的解并小于nearS
nearS=sum[j]-sum[i-1]; //更新当前nearS
}
}
for(int i=1;i<=n;i++){
int j=upper_bound(i,n+1,sum[i-1]+nearS);//求右端点
if(sum[j-1]-sum[i-1]==nearS){ //查找成功
printf("%d-%d\n",i,j-1); //输出左断点和右端点(注意是j-1而不是j)
}
}
system("pause");
return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  rEZj93RghFYQ   2023年11月02日   19   0   0 i++leetcode-java
  ltERVYe6WHLK   2023年11月02日   21   0   0 数据类型C#初始化
EIlYVvTMMLN7
最新推荐 更多