[BZOJ 1027] [JSOI2007] 合金

Posted on | Edited on | In , | Views:

题目链接

BZOJ 1027

做法

先把题意理解清楚，然后手算一下样例。
可以发现每个$(x,y,z)$的原材料可以看做二维平面上的一个点$(x,y)$，因为第三维与前两维的和是定制，所以可以省略。
但是第三维也并不是完全没用，有了第三维的限制，两个点组合能够表示的点就在这两个点连结所形成的线段上。
根据上面的结论，那么显然多个点能表示的点就在这些点围成的凸包内。
所以我们相当于从$n$个点中选出尽量少的点，使得这些点围成的凸包能够包括所有后面的m个点。
由于数据范围很小，我们枚举$n$个点中的两个点$i$和$j$，如果$m$个点均在线段$ij$的逆时针侧，我们就让$i$向$j$连边，这样我们只要在最后得到图上跑一边floyd求最小环就行了。
判断是否在逆时针侧的话用叉积。
还要注意特判一下点恰好在这条线段上的情况，可以用点积判断夹角实现。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#define LL long long
#define N (150005)
using namespace std;
int n,maxans;
LL f[N],tot;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
struct node{
    int a,b;
    inline bool operator < (const node &t) const{
        return a<t.a;
    } 
}a[N];
priority_queue<node> H;
inline bool cmp(node a,node b){
    return a.b==b.b?a.a<b.a:a.b<b.b;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(a[i].a),read(a[i].b);
    } 
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++){
        if (tot+a[i].a<=a[i].b) H.push(a[i]),tot+=a[i].a;
        else{
            if (!H.empty()&&tot-H.top().a+a[i].a<=a[i].b&&H.top().a>a[i].a){
                tot-=H.top().a-a[i].a;
                H.pop();
                H.push(a[i]);
            }
        }
    }
    printf("%d",H.size());
    return 0;
}