A1044 Shopping in Mars (25分)(看不懂

2020-02-04  本文已影响0人  km15

// 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;

}

上一篇 下一篇

猜你喜欢

热点阅读