// A1044 Shopping in Mars (25分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
题意:
1、给一串数字(10的5次,一个和(10的8次
2、找出能够满足这个和的区间,如果不能,则最小的大于这个区间的数
(数字不超过10的3次方
(左端点小的先输出,
解题:
learn && wrong:
1、
*/
include <iostream>
using namespace std;
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
}
}
return 0;
}
网友评论