专栏首页vblogPAT 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 (≤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

题目解析

求一串正整数序列中连续的一段,使得这个连续的段内数字的和恰好等于所期望的值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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    vivi
  • 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...

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

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

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

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

    用户1908973
  • 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...

    ShenduCC
  • Common Pitfalls to Avoid when using HTML5 Application Cache

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

    IMWeb前端团队
  • Common Pitfalls to Avoid when using HTML5 Application Cache

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

    IMWeb前端团队
  • Cozmo人工智能机器人SDK使用笔记(9)-判断部分if_this_then_that

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

    zhangrelay
  • 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...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券