专栏文章

题解：P13486 [GCJ 2008 Finals] Juice

DDevilsFlame
P13486题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioppxlq
此快照首次捕获于
2025/12/02 23:08
3 个月前
此快照最后确认于
2025/12/02 23:08
3 个月前
查看原文
这题跟标签数学与本题好像没有什么关系。
最简单的暴力，枚举 A,B,CA,B,C，在此之上我们发现只要枚举 ii 满足 ci≤104−A−B,A≥ai,B≥bic_i \le 10^4 - A - B,A \ge a_i,B \ge b_i 即可。时间复杂度 O(N3)O(N^3)。
CPP
#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;
}
优化。
我们发现，可以先枚举 AiA_i，取出 Aj≤AiA_j \le A_i 的数，另开数组按 BB 升序排序，对于任意 BjB_j，前面的数都比 BjB_j 小，所以对于 C=10000−A−BC = 10000 - A - B，CC 只会越来越小，所以可以建大根堆，弹出不符合当前 CC 的数，因为之后的 CC 也不会满足。
细细品尝一下，这是用堆：
CPP
            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());
            }
这是暴力：
CPP
            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);
            }
用堆可以省掉很多重复的遍历。
本题不卡常，但要是用较快的读入方式。
最后完整代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...