PAT 解题报告 1044. Shopping in Mars (25)

1044. Shopping in Mars 题目描述:

题目抽象出来就是给你一个数组D和一个指定的值M, 在数组中找到连续的子序列使得Di + … + Dj >= M, 并且使得差值Di + … + Dj - M最小(最小当然是零了), 具体描述如下:

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:

  1. 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).
  2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
  3. 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.

More specifically:

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.

1044. Shopping in Mars 算法分析:

看到描述的时候觉得还是比较难的, 但是真正的题目是在所描述的问题背景上又加上了点限制,去除了循环的概念, 也就是要求连续的 i <= j such that Di + … + Dj = M, i <= j那么就不可能过头了再回到D[0], 从暴力法的角度看的话, 那么就是是找到所有的(i, j) such that i <= j, 然后挨个测试和Di + … + Dj,  对于每个Pair(i, j) i <=j 我们都能在常数时间内得到Di + … + Dj 想想为什么? 于是暴力的做法是O(N^2),明显超时。 再仔细想想的话, 还有信息可以利用: 正对每个i, 一定都顶多只有一个对应的临界的j, 恰好使得Di + … + Dj >= M, 我们于是遍历每个i, 当找到这个i对应的j以后, 我们要找下一个i+1对应的j的时候, 应该从j+1开始找, 因为从i+1开始的连续子序列一定是包含了Dj的 (不然Dj就不是那个临界的j, 那个恰好使得Di + … + Dj >= M), 于是从下面的代码实现中也可以看出来, 这样的话采用聚合分析, 我们可以看出来for循环中的i, 和ix之多都遍历了一次D数组, 所以聚合分析的结果的时间复杂度是线性的O(N). 下面是可以AC的代码:

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>
#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

struct Info {
    int sum;
    int idx;
};

vector<Info> infos;
vector<int> diamonds;
int N, M;

void gao() {
    if(0 == N) return;
    infos[0].sum = 0;
    int ix0 = -1;
    while(infos[0].sum < M) {
        ix0++;
        infos[0].sum += diamonds[ix0];
    }
    infos[0].idx = ix0;

    for(int i=1; i<N; ++i) {
        infos[i].sum = infos[i-1].sum - diamonds[i-1];
        int ix = infos[i-1].idx;
        while(infos[i].sum < M && ix < N) {
            ix++;
            infos[i].sum += diamonds[ix];
        }
        infos[i].idx = ix;
        if(infos[i].sum < M) {
            infos[i].idx = -1;
            break;
        }
    }
    int mindiff = infos[0].sum - M;
    REP(i, N) {
        if(-1 == infos[i].idx) break;
        if(infos[i].sum - M < mindiff) {
            mindiff =  infos[i].sum - M;
        }
        if(0 == mindiff) break;
    }

    REP(i, N) {
        if(-1 == infos[i].idx) break;
        if(infos[i].sum - M == mindiff) {
            printf("%d-%d\n", i+1, infos[i].idx+1);
        }
    }
    return ;
}

int main(void) {
    scanf("%d %d", &N, &M);
    infos.resize(N);
    diamonds.resize(N);
    REP(i, N) scanf("%d", &diamonds[i]);
    gao();
    return 0;
}

1044. Shopping in Mars 注意点:

不要用cin, cout, 可能会超时.

Written on January 18, 2014