# PAT 1044 Shopping in Mars (25分) 二分法

### 题目

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M3, 2, 1, 5, 4, 6, 8, 7, and we must pay M

Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15). Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15). Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15). Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.

If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.

Input Specification: Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤105), the total number of diamonds on the chain, and M (≤10​8 ), the amount that the customer has to pay. Then the next line contains N positive numbers D1​​ ⋯D​N​​ (D​i​​ ≤10​3​​ for all i=1,⋯,N) which are the values of the diamonds. All the numbers in a line are separated by a space.

Output Specification: For each test case, print i-j in a line for each pair of i ≤ j such that Di + ... + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.

If there is no solution, output i-j for pairs of i ≤ j such that Di + ... + Dj >M with (Di + ... + Dj −M) minimized. Again all the solutions must be printed in increasing order of i.

It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

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```

Sample Input 2:

```5 13
2 4 5 7 9```

Sample Output 2:

```2-4
4-5```

### 题目解析

• 根据题意我们只需要保存子序列的首尾元素下标，不需要保存这个序列所有元素，所以我们可以把原输入转变一下，把value[i]变成从value到value[i]的累加和，这样每一对`i,j`下标就是一个序列的区间，而`value[j] - value[i - 1]` 就是这段序列的和。
• 原输入虽然都是正数，但是无序的，但是当我们将其转为累加和后，就成了一个递增序列，所以就相当于是给出了一个有序序列，给出了一个目标值，很熟悉的套路，二分法呗。
• 用一个变量`min_ans`保存当前找到的满足大于等于目标值m的最小序列和，用`vector<int>`保存这个序列的首尾元素位置，也就是`i，j`。对于每一个`i（1 <= i <= n）`，将其作为左边界，找到从i开始，满足`num[i]+num[i+1]+...+num[j] >= target` 的第一个位置 `j，i-j`就是此序列区间，`sum[j] - sum[i - 1`]就是这段序列和，比较这段序列和和之前的最小值`min_ans`如果相等，当前区间也满足，就把`ij`加入`vector`如果比`min_ans`，就说明当前序列更好，清空`vector`，加入`ij`，更新`min_ans`为当前序列和。
• 最终输出`vector`中的值，每一次取出两个。

### 完整代码

```#include <iostream>
#include <vector>
using namespace std;

// 二分法，找到从i开始，满足sum[i]+sum[i+1]+...+sum[j] >= target 的第一个位置 j
int helper(int sum[], int len, int i, int target) {
// 二分法，左闭右闭写法，len是sum数组最后一个有效位置
int left = i, right = len;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sum[mid] - sum[i - 1] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}

int main() {
// n个数组元素，目标值m
int n, m;
vector<int> res;

cin >> n >> m;
// 有效下标从1开始，values = 0
int values[n + 1] = {0};
// 输入n个元素值
for (int i = 1; i <= n; ++i) {
cin >> values[i];
// 转成从1到i的累加值
values[i] += values[i - 1];
}
// 保存最小的子序列和，可能等于m，也可能是大于m中的最小值
int min_ans = 999999;
for(int i = 1; i <= n; ++i) {
// 找到从i开始满足连续和大于等于m的第一个位置j
int j = helper(values, n, i, m);
// j要在有效范围内
if (j <= n) {
// 当前子序列和
int temp = values[j] - values[i - 1];
// 比之前的最小和 大，放弃
if (temp > min_ans) continue;
// 当前子序列和最小
if (temp < min_ans) {
// 清空之前记录的序列
res.clear();
// 更新最小值
min_ans = temp;
}
// 记录当前序列的起始和结束位置
res.push_back(i);
res.push_back(j);
}
}
// 输出每一个满足要求序列的起始和结束下标
for (int i = 0; i < res.size(); i += 2)
printf("%d-%d\n", res[i], res[i + 1]);

return 0;
}```

0 条评论

• ### PAT 1011 World Cup Betting (20分) 比较大小难度级别

With the 2010 FIFA World Cup running, football fans the world over were becoming...

• ### PAT 1034 Head of a Gang (30分) 图的连通分量 + DFS

One way that the police finds the head of a gang is to check people's phone call...

• ### PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subs...

• ### 基于ROS和gazebo对gym中robotics扩展

This work presents an extension of the initial OpenAI gym for robotics using ROS...

• ### poj-1012-约瑟夫问题

The Joseph's problem is notoriously known. For those who are not familiar with t...

• ### POJ-1926 Pollution

Pollution Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 40...

• ### Common Pitfalls to Avoid when using HTML5 Application Cache

Application Cache, also known as AppCache, has been a pretty hot topic with web ...

• ### Common Pitfalls to Avoid when using HTML5 Application Cache

Application Cache, also known as AppCache, has been a pretty hot topic with web ...

• ### Cozmo人工智能机器人SDK使用笔记（9）-判断部分if_this_then_that

此示例演示了如何使用“If This Then That”（http://ifttt.com）使Cozmo在Gmail帐户收到电子邮件时作出回应。以下说明将引导...

• ### AIM Tech Round 4 (Div. 2)(A，暴力，B，组合数，C，STL+排序)

A. Diversity time limit per test：1 second memory limit per test：256 megabytes in...

### 活动推荐 