代领快递

Posted on In

题目大意:有一些物品,每个物品会有两个属性(x,y),有两种箱子,每种箱子分别有若干个.先规定把箱子分为两个种类,种类1的箱子只能装下属性x严格比他小的物品,对y不做考虑,种类2的箱子只能装下属性y严格比他小的物品,对x不做考虑.每个箱子可以装无限个,但是没装入一个会花掉一分钟,问装完所有箱子最少花费多长时间.

简直是二分答案的神题,我们考虑二分这个时间t,也就是每个箱子最多装的物品,然后问题就转化成了,在时间t的范围内,是否可以装完全部物品的判定性问题.

考虑对种类1的箱子升序排序,对种类2的箱子降序排序,对物品按照w第一s第二关键字升序排序

然后考虑对当前的t我们如何验证.

贪心做的话,是把w小的放进种类1里面限制小的.建立一个以s为关键字的大根堆,每当不能放的时候,就从大根堆里弹出t个来(弹出来的就意味着往这个箱子里面放置的是哪些).这t个一定是s最大的,也就保证了往s里面放的都是尽量小的,贪心显然正确.

然后把没放完的物品放到种类2里面,因为我当前的的箱子是降序排序,所以每当不能放的时候,意味着,如果这个箱子放不了,后面的箱子也肯定都放不了,所以返回即可

最后判断是否还有没放完的,如果有东西没放完代表这次的t是失败的,反之同理.

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
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e6 + 66, G = 5e4 + 66;

int A, B, T;
int x[G], y[G];

struct yhzhyhm
{
    int w, s;
    bool operator < (const yhzhyhm &yhm) const {return s < yhm.s;}
}yh[N];

inline bool check(int t)
{
    int pi(1), i, j; priority_queue <yhzhyhm> q;
    for (i = 1; i <= A; ++ i)
    {
        while (pi <= T && yh[pi].w < x[i]) q.push(yh[pi]), ++ pi;
        for (j = 1; j <= t && ! q.empty(); ++ j) q.pop();
    }
    while (pi <= T) q.push(yh[pi]), ++ pi;
    for (i = 1; i <= B; ++ i)
    {
        if (! q.empty() && q.top().s >= y[i]) return false;
        for (j = 1; j <= t && ! q.empty() && q.top().s < y[i]; ++ j) q.pop();
    }
    return q.empty();
}

inline int cmp(int yhm1, int yhm2) {return yhm1 > yhm2;}
inline int CMP(yhzhyhm yhm1, yhzhyhm yhm2) {return (yhm1.w < yhm2.w) || ((yhm1.w == yhm2.w) && (yhm1.s < yhm2.s));}

signed main()
{	
    int i; A = read(), B = read(), T = read();
    for (i = 1; i <= A; ++ i) x[i] = read();
    for (i = 1; i <= B; ++ i) y[i] = read();
    for (i = 1; i <= T; ++ i) yh[i].w = read(), yh[i].s = read();

    sort(x + 1, x + 1 + A), sort(y + 1, y + 1 + B, cmp);
    sort(yh + 1, yh + 1 + T, CMP);

    int l = 0, r = T, mid;
    while (l < r)
    {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    put(! check(r) ? -1 : r);

    return 0;
}

后记:

对此题的解法佩服到了极点,贪心,二分两者结合起来,在这个题里天衣无缝,水乳交融

对出题人的奇思妙想佩服到了极点