PAT甲级1044 Shopping in Mars (25分)|C++实现

一、题目描述

原题链接

Input Specification:

​​Output Specification:

Sample Input 1:

16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1-5
4-6
7-8
11-11

二、解题思路

这道题目还是有点难想的。题目就是给一串数字，要求在合适的地方截断，使截下来的数字之和等于题目给出的数字M，若不存在这样的数字串，则我们取大于M的最小数值。我们用数组sum表示以第i个数结尾的和。首先呢，我们要找出我们要凑的数字，那么我们可以遍历i，将此时的i作为下界，将N+1作为上界，用二分法找出最接近M的上界nearS，最后再遍历一次，寻找答案为nearS的序号。

三、AC代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int sum[maxn] = {0};
int nearS = 10000000;
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()
{
  int N;
  int M;
  scanf("%d%d", &N, &M);
  for(int i=1; i<=N; i++)
  {
    scanf("%d", &sum[i]);
    sum[i] += sum[i-1];
  }
  for(int i=1; i<=N; i++)
  {
    int j = upper_bound(i, N+1, sum[i-1]+M);
    if(sum[j-1] - sum[i-1] == M)
    {
    	nearS = M;
        break;
    }
    else if(j<=N && sum[j] - sum[i-1] < nearS)
      nearS = sum[j] - sum[i-1];
  }
  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);
  }
  return 0;
}