【PAT甲级 - C++题解】1044 Shopping in Mars

简介: 【PAT甲级 - C++题解】1044 Shopping in Mars

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).Whenmakingthepayment,thechaincanbecutatanypositionforonlyonceandsomeofthediamondsaretakenoffthechainonebyone.Onceadiamondisoffthechain,itcannotbetakenback.Forexample,ifwehaveachainof8diamondswithvaluesM). 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$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 (≤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 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


题意

给定 N 个数的序列 Di+…+Dj 和一个常量 M ,让我们输出所有区间和等于 M 的方案。


每行输出一种可行方案,具体格式为 i-j,表示 Di+…+Dj=M 。


如果方案不唯一,则按照 i 递增的顺序输出所有方案。


如果无法准确凑出 M ,仍然输出 i-j,表示 Di+…+Dj>M 并且 Di+…+Dj−M 的值最小。


如果方案不唯一,则按照 i 递增的顺序输出所有方案。


思路

这道题需要用到前缀和和双指针算法,先对序列求前缀和并存到数组 s 中。


然后先求大于等于M 的最小区间和 res ,因为可能不存在等于 M 的区间和。


最后再去遍历所有区间,输出所有等于 res 的区间和方案。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int s[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    //求前缀和
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    //找到大于等于m的最小值
    int res = INF;
    for (int i = 1, j = 0; i <= n; i++)
    {
        //如果s[i]-s[j+1]>=m,则s[i]-s[j]也一定大于等于m,所以直接j++即可
        while (s[i] - s[j + 1] >= m)   j++;
        if (s[i] - s[j] >= m)    res = min(res, s[i] - s[j]);
    }
    //找到区间和等于res的所有方案
    for (int i = 1, j = 0; i <= n; i++)
    {
        while (s[i] - s[j + 1] >= m)   j++;
        if (s[i] - s[j] == res)  printf("%d-%d\n", j + 1, i);
    }
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
296 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
359 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
329 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
253 0
|
C++
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
301 0
|
人工智能 BI C++
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
501 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
740 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
410 16