题目

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.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N(≤105)N\left( \leq 10^{5}\right), the total number of diamonds on the chain, and M(≤108)M\left( \leq 10^{8}\right), 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)D_{1} \cdots D_{N}\left(D_{i} \leq 10^{3} \text { for all } i=1, \cdots, N\right) 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:

1
2
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1
2
3
4
1-5
4-6
7-8
11-11

Sample Input 2:

1
2
5 13
2 4 5 7 9

Sample Output 2:

1
2
2-4
4-5

题解

思路

  • 首先容易想到暴力解

  • 即遍历每一个数

    • 先设sum为0
    • 从这个数再遍历
      • sum不断加上下一个数，使sum刚好大于或等于要付的钱
    • 判断sum和之前的min_cost来确定是否要更新答案

  • 输出

  • 容易写出这样的代码

  • num_diamonds, pay = list(map(int, input().split()))	
chain = list(map(int, input().split()))
ans = []
min_cost = 99999
for i in range(num_diamonds):
    sum = 0
    for j in range(i, num_diamonds):
        sum += chain[j]
        # 判断要不要更新ans
        if pay <= sum:
            if sum < min_cost:
                ans = [[i, j]]
                min_cost = sum
            elif sum == min_cost:
                ans.append([i, j])
                min_cost = sum
            break
for i in ans:
    print("-".join(list(map(lambda x: str(x + 1), i))))

<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">+ 但是这样会有大量的重复计算，造成严重的超时。</span><br><span class="line"></span><br><span class="line">+ 更好的方式是二分查找</span><br><span class="line"></span><br><span class="line">+ 首先把从第一个数开始求和的结果放在一个列表里</span><br><span class="line"></span><br><span class="line">+ 即&#96;[a[0], a[0]+a[1], a[0]+a[1]+a[2],...]&#96;</span><br><span class="line"></span><br><span class="line">+ 为了方便起见，前面再加一个0,即&#96;0, a[0], a[0]+a[1], a[0]+a[1]+a[2],...]&#96; 这个0待会要用到</span><br><span class="line"></span><br><span class="line">+ 此时这个新建的列表，我们称为&#96;_sum&#96; ，是一个有序的，从小到大排列的。</span><br><span class="line"></span><br><span class="line">+ 如果我们找，从第一个数字开始，加到正好能使总和大于等于要付的钱的第一个数</span><br><span class="line"></span><br><span class="line">+ 就相当于在&#96;_sum&#96;找第一个大于等于要付的钱的数</span><br><span class="line"></span><br><span class="line">+ 这就可以使用二分查找了</span><br><span class="line"></span><br><span class="line">+ 可是从第二个数字开始呢？难道要再算走一遍&#96;_sum&#96;吗？</span><br><span class="line"></span><br><span class="line">+ 不必。</span><br><span class="line"></span><br><span class="line">+ 对于第二个数字开始，它的&#96;_sum&#96; 其实就是原来的&#96;_sum&#96; 减去&#96;_sum[1]&#96;。因为&#96;_sum[1]&#96;表示的就是第一个数。</span><br><span class="line"></span><br><span class="line">+ 同理，对于第N个数，它的&#96;_sum&#96;和列表就是最初的&#96;_sum&#96;剪去&#96;_sum[N-1]&#96;。因为从N到K的和就是从1到K的和减去从1到N的和。</span><br><span class="line"></span><br><span class="line">+ 那么对每个数走一遍二分查找即可。</span><br><span class="line"></span><br><span class="line">+ 因为我们是沿着下标顺序找的，所以最后不用排序。</span><br><span class="line"></span><br><span class="line">+ 还有一种方法是**双指针法**，没有二分查找帅，就不用了。</span><br><span class="line"></span><br><span class="line">## 数据结构</span><br><span class="line"></span><br><span class="line">+ _sum 记录从0开始的累加和</span><br><span class="line">+ l 是二分查找左边界</span><br><span class="line">+ r 是二分查找右边界</span><br><span class="line">+ mid 是二分查找的中间</span><br><span class="line">+ num临时变量，记录对i这个数来说，比要付钱略微大的数</span><br><span class="line">+ ans 是一个列表，记录要输出的答案</span><br><span class="line">+ ans的一项代表一组答案，是一个列表，包含两个数，即下标。</span><br><span class="line"></span><br><span class="line">## 算法</span><br><span class="line"></span><br><span class="line">+ 都写在思路里了。</span><br><span class="line"></span><br><span class="line">## 代码</span><br><span class="line"></span><br><span class="line">+ 因为此题对Python歧视，不管暴力解还是二分查找都有三个点超时。建议使用C++。原理都是一样的。</span><br><span class="line"></span><br><span class="line">### Python</span><br><span class="line"></span><br><span class="line">&#96;&#96;&#96;python</span><br><span class="line">num_diamonds, pay &#x3D; list(map(int, input().split()))</span><br><span class="line">chain &#x3D; list(map(int, input().split()))</span><br><span class="line">_sum &#x3D; [0] + [sum(chain[:i + 1]) for i in range(num_diamonds)]</span><br><span class="line">ans &#x3D; []</span><br><span class="line">min_cost &#x3D; _sum[-1]</span><br><span class="line">for i in range(num_diamonds):	# 二分查找</span><br><span class="line">    l &#x3D; i</span><br><span class="line">    r &#x3D; num_diamonds - 1</span><br><span class="line">    while l &lt; r:</span><br><span class="line">        mid &#x3D; (l + r) &#x2F;&#x2F; 2</span><br><span class="line">        if _sum[mid + 1] - _sum[i] &lt; pay:</span><br><span class="line">            l &#x3D; mid + 1</span><br><span class="line">        else:</span><br><span class="line">            r &#x3D; mid</span><br><span class="line">    num &#x3D; _sum[l + 1] - _sum[i] # 看情况更新答案</span><br><span class="line">    if num &gt;&#x3D; pay:</span><br><span class="line">        if num &lt; min_cost:</span><br><span class="line">            ans &#x3D; [[i + 1, l + 1]]</span><br><span class="line">            min_cost &#x3D; num</span><br><span class="line">        elif num &#x3D;&#x3D; min_cost:</span><br><span class="line">            ans.append([i + 1, l + 1])</span><br><span class="line">            min_cost &#x3D; num</span><br><span class="line"></span><br><span class="line">for i in ans:</span><br><span class="line">    print(&quot;-&quot;.join(list(map(str, i))))</span><br><span class="line"></span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int num_diamonds,pay;
    scanf("%d %d",&num_diamonds,&pay);
    vector<int>sum(num_diamonds+1,0);
    for(int i = 1;i<=num_diamonds;i++){
        scanf("%d",&sum[i]);
        sum[i] += sum[i-1];
    }
    vector<vector<int>> ans;
    int min_cost = sum[num_diamonds];
    for (int i = 0;i < num_diamonds;i++){ // 二分查找
        int l = i;
        int r = num_diamonds - 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (sum[mid + 1] - sum[i] < pay)
                l = mid + 1;
            else r = mid;
        }
        int num = sum[l+1] - sum[i];    // 视情况更新答案
        if (num >= pay){
            if (num < min_cost){
                ans = {vector<int>{i+1,l+1})};
                min_cost = num;
            }else if (num == min_cost){
                ans.emplace_back(vector<int>{i+1,l+1});
                min_cost = num;
            }
        }
    }
    for (auto &it:ans)
        printf("%d-%d\n",it[0],it[1]);
}