PAT-A 真题 – 1044 Shopping in Mars

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 M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:

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$ ( $\leq 1 0^{5}$ ), the total number of diamonds on the chain, and $M$ ( $\leq 1 0^{8}$ ), the amount that the customer has to pay. Then the next line contains $N$ positive numbers $D^{1} \dots D^{N}$ ( $D^{i} \leq 1 0^{3}$ for all $i = 1, \dots, 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 $\leq$ j such that $D$ i + ... + $D$ j = $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 $\leq$ j such that $D$ i + ... + $D$ j $> M$ with ( $D$ i + ... + $D$ j $- 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

题目大意：

在火星上买东西。第一行给定输入数据个数和需要凑的价格，第二行给定数据，要求找到所有连续的数据可以凑够价格的方案，如果不能恰好凑齐，找到高于价格最少的方案。

这道题最直观的暴力方法：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
const int maxn = 100100;
using namespace std;
typedef struct {
  int s, e;
} node;
vector<node> ans;
int D[maxn] = {0};

int main(){
  int cnt, price, min_lost = 0x7fffffff;
  scanf("%d %d", &cnt, &price);
  for(int i = 1; i <= cnt; i++)
    scanf("%d", &D[i]); 
  //########## 这段垃圾代码得改改，不然会超时 ########### 
  //#####################################################
  for(int s = 1; s <= cnt; s++){
    int add = 0;
    for(int e = s; e <= cnt; e++){
      add += D[e];
      if(add >= price && (add - price) <= min_lost){  //累计和大于等于应付价钱，并且是最优结果 
        if(min_lost > (add - price)){  //如果是更优结果 
          min_lost = (add - price);  //更新最优结果 
          ans.clear();        //清空之前的答案 
        }
        ans.push_back({s,e});      //记录下这一美妙的答案 
        break;              //不用再继续遍历啦 
      }
    }
  }
  //#####################################################
  for(int i = 0; i < ans.size(); i++)
    printf("%d-%d\n",ans[i].s, ans[i].e);
  return 0;
}

正常情况这段代码会得21分，有两个测试点超时。原因就在于代码中用###标注的部分，时间复杂度为O(1/2n^2)，对于100000数量级的数据，要和长者借1s才能运行完.....

优化线性遍历问题的方案，可以采用二分的方法，但是二分法要求的数据是有序的，我们给定的要求累加的数据是无序的，顺序又是不可破坏的，所以不能排序。

但是这里给定的数据都是正数，所以可以使用累加的方法，构造出一个累加数列，这样的数列就是有序的了

例如2 4 5 7 9，累加数列就是2 6 11 18 27。

在求一段数的和时，直接用后面的减去前面的就可以使用二分查找了。

这里介绍一个C++ Std自带的函数：lower_bound(Begin, End, num)

这个函数的作用是，在[Begin, End)中找到第一个大于等于num的位置，返回的是指针或迭代器。这个函数可以帮助我们减少写二分的麻烦。

作为良心博主，两个版本的程序我都写了：

用lower_bound的版本：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
const int maxn = 100100;
using namespace std;
typedef struct {
  int s, e;
} node;
vector<node> ans;
int D[maxn] = {0};

int main(){
  int cnt, price, min_lost = 0x7fffffff;
  scanf("%d %d", &cnt, &price);
  for(int i = 1; i <= cnt; i++){
    scanf("%d", &D[i]);
    D[i] += D[i - 1];  //累加 
  }
  for(int s = 1; s <= cnt; s++){
    //通过二分，在[ &D[s], &D[cnt] )中找到第一个大于 D[s] + price 的
    int *last = lower_bound(D + s, D + cnt + 1, D[s - 1] + price); 
    int last_idx = last - D;  //last的下标 
    int add = *last - D[s - 1];    //之间的和
    //printf("^%d-%d=%d\n", *last, D[s], add);
    if(add >= price && (add - price) <= min_lost){  //累计和大于等于应付价钱，并且是最优结果 
      //cout << s + 1 << "->" << last_idx << endl;
      if(min_lost > (add - price)){  //如果是更优结果 
        min_lost = (add - price);  //更新最优结果 
        ans.clear();        //清空之前的答案
        //cout << min_lost << '!' << endl; 
      }
      ans.push_back({s, last_idx});      //记录下这一美妙的答案 
    }
  }
  for(int i = 0; i < ans.size(); i++)
    printf("%d-%d\n",ans[i].s, ans[i].e);
  return 0;
}

不用lower_bound的版本：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//存放范围的结构 
typedef struct{
  int l, r;
} range;
//二分查找，在v[l]和v[r]之间找到第一个大于等于n的元素 
int Dichotomy_find(vector<int> &v, int l, int r, int n){
  int mid = (l + r) / 2;
  while(l <= r){
    mid = (l + r) / 2;
    if(v[mid] < n) l = mid + 1;
    if(v[mid] > n) r = mid - 1;
    if(v[mid] == n) return mid;
  }
  if(v[l] < n && v[r] < n) return -1;  //查找失败，返回-1 
  if(v[l] == n) return l; 
  if(v[r] == n) return r;
  return v[l] > n ? l : r;
}

int main(){
  int cnt, price;
  cin >> cnt >> price;
  vector<int> money(cnt+1);
  //读取累加和 
  for(int i = 1; i <= cnt; i++){
    int num;
    cin >> num;
    money[i] = num;
    if(i) money[i] += money[i - 1];
  }
  //查找
  vector<range> ans;
  int min = 0x7fffffff;
  for(int i = 1; i <= cnt; i++){
    int idx = Dichotomy_find(money, i + 1, cnt, money[i-1] + price);
    if(idx != -1){  //如果查找成功 
      int pay = money[idx] - money[i-1];
      if(pay < min){  //找到更优的办法 
        min = pay;  //记录花的钱 
        ans.clear();  //清空之前的 
        ans.push_back({i, idx}); 
      }else if(pay == min){  //找到和之前一样好的办法 
        ans.push_back({i, idx});  //记录 
      }
    }
  }
  for(auto i : ans)
    cout << i.l << '-' << i.r << endl;
  return 0;
}

斐斐のBlog