PAT 1044 Shopping in Mars (25分) 二分法
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 (≤108 ), the amount that the customer has to pay. Then the next line contains N positive numbers D1 ⋯DN (Di ≤103 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 13Sample Output 1:
1-5
4-6
7-8
11-11Sample Input 2:
5 13
2 4 5 7 9Sample Output 2:
2-4
4-5题目解析
求一串正整数序列中连续的一段，使得这个连续的段内数字的和恰好等于所期望的值m。如果不能找到恰好等于，就找到连续和大于m中的最小值对应的子序列区间。打印所有可能的结果。
- 根据题意我们只需要保存子序列的首尾元素下标，不需要保存这个序列所有元素，所以我们可以把原输入转变一下，把value[i]变成从value[1]到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] = 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;
}