题解：P13486 [GCJ 2008 Finals] Juice

· · 题解

这题跟标签数学与本题好像没有什么关系。

最简单的暴力，枚举 A,B,C，在此之上我们发现只要枚举 i 满足 c_i \le 10^4 - A - B,A \ge a_i,B \ge b_i 即可。时间复杂度 O(N^3)。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1e1,M = 1e4;
int T,n,g,ans;
struct Node{
    int a,b,c;
}a[N];
inline void read(int &x) {
    x = 0;
    char s = getchar();
    while(s < '0' || s > '9') s = getchar();
    while(s >= '0' && s <= '9') {
        x = x * 10 + s - 48;
        s = getchar();
    }
    return;
}
inline bool cmp(Node a,Node b) {
    if(a.a != b.a) return a.a < b.a;
    else if(a.b != b.b) return a.b < b.b;
    else return a.c < b.c;
}
signed main() {
    read(T);
    for(int t = 1;t <= T;t ++) {
        read(n);
        for(int i = 1;i <= n;i ++) {
            read(a[i].a),read(a[i].b),read(a[i].c);
        }
        ans = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++) {
                int A = max(a[i].a,a[j].a),B = max(a[i].b,a[j].b);
                int C = M - A - B;
                if(C < 0) continue;
                for(int l = 1;l <= n;l ++) if(A >= a[l].a && B >= a[l].b && C >= a[l].c) g ++;
                ans = max(ans,g);
                g = 0;
            }
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}

优化。
我们发现，可以先枚举 A_i，取出 A_j \le A_i 的数，另开数组按 B 升序排序，对于任意 B_j，前面的数都比 B_j 小，所以对于 C = 10000 - A - B，C 只会越来越小，所以可以建大根堆，弹出不符合当前 C 的数，因为之后的 C 也不会满足。

细细品尝一下，这是用堆：

            priority_queue < int > q;
            int l = 1;
            for(int j = 1; j <= lv; j++) {
                while(l <= lv && v[l].b <= v[j].b) q.push(v[l ++].c);
                int C = M - A - v[j].b;
                if(C < 0) break;
                while(!q.empty() && q.top() > C) q.pop();
                ans = max(ans,(int)q.size());
            }

这是暴力：

            for(int j = 1; j <= lv; j++) {
                int C = M - A - v[j].b;
                if(C < 0) break;
                int g = 0;
                for(int l = 1;l <= j;l ++) if(v[l].c <= C) g ++;
                ans = max(ans,g);
            }

用堆可以省掉很多重复的遍历。

本题不卡常，但要是用较快的读入方式。

最后完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, M = 1e4;
struct Node {
    int a,b,c;
} a[N];
struct Node2 {
    int b,c;
} v[N];
inline void read(int &x) {
    x = 0;
    char s = getchar();
    while(s < '0' || s > '9') s = getchar();
    while(s >= '0' && s <= '9') {
        x = x * 10 + s - 48;
        s = getchar();
    }
    return;
}
inline bool cmp(Node a, Node b) {
    if(a.a != b.a) return a.a < b.a;
    else if(a.b != b.b) return a.b < b.b;
    else return a.c < b.c;
}
inline bool cmp2(Node2 a, Node2 b) {
    return a.b < b.b;
}
int T,n;
signed main() {
    read(T);
    for(int t = 1;t <= T;t ++) {
        read(n);
        for(int i = 1;i <= n;i ++) read(a[i].a),read(a[i].b),read(a[i].c);
        int ans = 0;
        sort(a + 1,a + 1 + n,cmp);
        for(int i = 1;i <= n;i ++) {
            int lv = 0,A = a[i].a;
            for(int j = 1;j <= n;j ++) if(a[j].a <= A) v[++ lv] = {a[j].b,a[j].c};
            sort(v + 1,v + 1 + lv,cmp2);
            priority_queue < int > q;
            int l = 1;
            for(int j = 1; j <= lv; j++) {
                while(l <= lv && v[l].b <= v[j].b) q.push(v[l ++].c);
                int C = M - A - v[j].b;
                if(C < 0) break;
                while(!q.empty() && q.top() > C) q.pop();
                ans = max(ans,(int)q.size());
            }
        }
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}