1. 题目
  2. 题目大意
  3. 解法
  4. 参考代码
  5. 感想

ICPC2013南京邀请赛 E. Eloh 解题报告

题目

http://icpc.njust.edu.cn/Contest/194/Problem/E

题目大意

给出 \(n\) 个物品的质量 \(m_i\) 和体积 \(v_i\)，

选出若干个使得 \(\sum \{m_j\} / \sum \{v_j\}, (1 <= j <= n - s)\) 达到最大值。

输出不选的个数 \(s\) 和不选的物品编号。

解法

01 分数规划、单调队列、栈

按 \(m_i / v_i\) 排序，枚举 \(s\)，并维护以下两个集合中的最值即可。

  • 维护已选物品中比值最差值：

    按比值从高到低把每个物品加入队列

    设当前已选物品的和比值为 \(M / V = \sum \{m_j\} / \sum \{v_j\}\)

    类似斜率优化，物品 \(i\) 暂时劣于物品 \(j\)，且 \(m_i / v_i < m_j / v_j\) => \((m_i - m_j) / (v_i - v_j) < M / V\)

    把每个物品比值看成平面上的点，如果连续 3 个物品比值的连线是凸的，中间那个肯定不选

    1. 如果队列尾存在物品比值比当前物品比值低的，扔掉（从 \(M / V\) 大于任何 \(m_i / v_i\) 考虑）

    2. 如果队列尾存在和比值比当前物品和比值低的，扔掉（比值高和比值低的一定不差）

      此时可以保证，队列中 \(m_i\) 递减，\(v_i\) 递减，为斜率优化创造了条件

    3. 如果队列尾连续 3 个点连线为凸，把倒数第二个扔了。保证队列中相邻点斜率递减

    4. 由于 \(M / V\) 递减，所以如果队头元素比队头+1元素优，队头扔了。此时队头元素最差

  • 维护未选物品比值最优值：

    1. 如果队列尾存在和比值比当前物品和比值高的，扔掉。此时可以保证，队列中 \(m_i\) 递增，\(v_i\) 递增

    2. 如果队列尾连续 3 个点连线为凹，把倒数第二个扔了。保证了队列中相邻点斜率递减

    3. 由于 \(M / V\) 递增，所以如果队尾-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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 200002
typedef long long ll;
struct point
{
    ll x, y;
    point() {}
    point(ll x, ll y): x(x), y(y) {}
    point operator-(const point & i) const
    {
        return point(x - i.x, y - i.y);
    }
    ll operator*(const point & i) const
    {
        return x * i.y - y * i.x;
    }
    bool operator<(const point & i) const
    {
        return (*this) * i > 0;
    }
} a[N], b[N];
int q[N], p[N];
int n;

vector<int> solve()
{
    vector<int> ans;
    ll sx = 0, sy = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; ++i)
    {
        sx += a[n - i + 1].x;
        sy += a[n - i + 1].y;
        b[n - i] = point(sx, sy);
    }
    memset(p, 0, sizeof(p));
    memset(q, 0, sizeof(q));
    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        while (t && a[q[t]].x >= a[i].x)
            --t;
        while (t > 1 && (a[i] - a[q[t]]) * (a[q[t - 1]] - a[q[t]]) >= 0)
            --t;
        q[++t] = i;
        while (t > 1 && b[i] * (a[q[t]] - a[q[t - 1]]) <= 0)
            --t;
        p[i] = q[t];
    }
    int h = 1;
    t = 0;
    for (int i = n - 1; i; --i)
    {
        while (h <= t && (a[q[t]].x <= a[i + 1].x || a[q[t]].y <= a[i + 1].y))
            --t;
        while (h < t && (a[i + 1] - a[q[t]]) * (a[q[t - 1]] - a[q[t]]) >= 0)
            --t;
        q[++t] = i + 1;
        while (h < t && b[i] * (a[q[h + 1]] - a[q[h]]) <= 0)
            ++h;
        if (b[i] * (a[p[i]] - a[q[h]]) > 0)
            ans.push_back(i);
    }
    return ans;
}

int main()
{
    while (cin >> n && n)
    {
        for (int i = 1; i <= n; ++i)
            cin >> a[i].y >> a[i].x;
        vector<int> ans = solve();
        cout << ans.size() << endl;
        for (int i = ans.size() - 1; i >= 0; --i)
            cout << ans[i] << endl;
    }
    return 0;
}

感想

其实这是一道比较经典复杂的 01 分数规划的题，除了用单调队列、栈来做，似乎用平衡树会有更好的效果。

比赛时看懂题意之后就觉得跟 USACO 某次月赛的某道题很像，然后就 1Y 了。