P1094. 纪念品分组

发表于 分类于 阅读次数： Waline： 本文字数： 380 阅读时长 ≈ 1 分钟

考点

  • 贪心

题解

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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 3e4 + 10;

int arr[LEN];

int main()
{
    int sum, n;
    cin >> sum >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    sort(arr, arr + n);
    int s = 0, ans = 0, l = 0, r = n - 1;
    while (l < r)
    {
        // flag控制r独立分组的情况
        s = arr[l];
        int flag = false;
        while (l < r && s + arr[r] <= sum)
        {
            s += arr[r];
            --r;
            flag = true;
        }
        flag == false ? --r : ++l;
        ++ans;
    }
    cout << (l == r ? ++ans : ans);
    return 0;
}

思路

不严谨的贪心题....要分组尽可能少，有两种选择：

  • 每次选较大和较小的，然后一直选较小的
  • 每次选较大和较小的，然后一直选较大的

第一种方案实现如下，但是WA了

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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 3e4 + 10;

int arr[LEN];

int main()
{
    int sum, n;
    cin >> sum >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    sort(arr, arr + n);
    int ans = 0, l = 0, r = n - 1;
    while (l < r)
    {
        int mx = arr[r];
        while (l < r && mx + arr[l] <= sum)
            mx += arr[l++];
        --r;
        ++ans;
    }
    if (arr[l] <= sum)
        ++ans;
    cout << ans;
    return 0;
}

第二种方案实现就如题解；主要难点在于边界值的处理，因为还有l >= r的情况要补充：

  • 如果两个指针正常运行，最终会在中间某处相遇，此刻l == r；那么最终结果要加1
  • 如果全都合为一组，最终r == 0, l == 1；但这种情况已经计算过了，结果不变
  • 如果全都自成一组，最终r == 0, l == 0；那么最终结果要加1

综上，输出结果前补充一下l == r的情况即可