舞会配对

Posted on Edited on In

题目大意：在 NOI2015 闭幕式舞会上有 N 个男孩和 N 个女孩，每个人都量过了自己的身高。每个男孩只跟女孩跳舞，并且女孩也只跟男孩跳舞。每个人最多只有一个舞伴。男孩或者想和比自己高的女孩跳舞，或者想和比自己低的女孩跳舞，同样的，女孩也是或者想和比自己高的男孩跳舞，或者想和自己低的男孩跳舞。你能决定最多有多少对能在一起跳舞么？

正解很简单，四类人两两搭配，一个显然正确且合理的贪心：对于一个人，如果有多种选择，选择最矮的那个一定更优，双指针维护一下就好

跟着豪哥学细节：c[cntc + 1] = inf

代码如下：

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
#define int long long
using namespace std;

const int N = 1e5 + 66, inf = 2147483647;

int a[N], b[N], c[N], d[N];
int cnta, cntb, cntc, cntd;

inline bool cmp(int x, int y){return x > y;}

signed main()
{
    int i, x, y, res(0), n = read();
    for (i = 1; i <= n; ++ i)
    {
        x = read(), y = abs(x);
        if (x == y) a[++ cnta] = y;
        else b[++ cntb] = y;
    }
    for (i = 1; i <= n; ++ i)
    {
        x = read(), y = abs(x);
        if (x == y) c[++ cntc] = y;
        else d[++ cntd] = y;
    }
    
    sort(a + 1, a + 1 + cnta), sort(d + 1, d + 1 + cntd);
    
    int l = 1;
    for (i = 1; i <= cnta; ++ i)
    {
        if (l > cntd) break;
        while (l <= cntd && d[l] <= a[i]) ++ l;
        if (a[i] < d[l]) ++ res, ++ l; 
    }
    
    sort(b + 1, b + 1 + cntb, cmp), sort(c + 1, c + 1 + cntc, cmp);
    
    l = 1;
    c[cntc + 1] = inf;
    for (i = 1; i <= cntb; ++ i)
    {
        if (l > cntc) break;
        while (l <= cntc && c[l] >= b[i]) ++ l;
        if (b[i] > c[l]) ++ res, ++ l;
    }
    
    put(res);
    return 0;
}

总结：

考试时候一开始就想写暴力，然后写了二分图，因为距离上一次写板子已经过去三个月了，所以这次写板子还调了一会，一开始还建了个双向边….导致写暴力就花了1h没时间想正解，或者说想到了，没时间也没赶写

本质上，还是对板子不够熟练，知识点有盲区，我假如可以半小时写完暴力，再搭配上最后的二十分钟，就总计可以有五十分钟的时间来写正解

可惜，那是假如

期望得分：100+50+？pts

实际得分：90+40+30pts

在稳步提升，不是我变强了，也不是他们变菜了（他们一直都很菜），是我的做题策略改变了，终于不再傻逼兮兮的上来就猛干正解，最后正解没肝出来，暴力也没打上

以后在保证暴力正确性的前提下，缩短暴力时间，正解还是要写的

我想AK

虎瘦雄心在，人穷志不短，无论落魄到何种地步，都不要触碰做人的底线，心怀勇气的走下去，只有这样，一切才会好起来