首页 > 代码库 > BZOJ1071 [SCOI2007]组队
BZOJ1071 [SCOI2007]组队
说好的一天一题解来啦~（其实是给马上要来的NOIP模拟赛加点RP>.<）
Vfk大神说是n^2乱搞，于是蒟蒻就开始乱搞，结果发现怎么搞都是O(n ^ 3)的。。。
后来请教了snake大神，他说先给sum = A * h + B * s排序，然后枚举h和s的最小值。(h -- Height, s -- Speed)
然后就是两个指针乱搞：
先枚举s最小值，然后一边枚举v的最小值一边查询符合条件的人数，因为这一定是相邻的一串。
1 /************************************************************** 2 Problem: 1071 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1708 ms 7 Memory:1044 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 15 struct data{16 int s, h, sum;17 }x[10000], y[10000];18 19 inline bool cmp1(const data &a, const data &b){20 return a.h < b.h;21 }22 23 inline bool cmp2(const data &a, const data &b){24 return a.sum < b.sum;25 }26 27 int n, Max, Min, l, r, cnt, ans;28 int A, B, C;29 30 inline bool check1(int p){31 return y[p].s <= Max && y[p].s >= Min;32 }33 34 inline bool check2(int p){35 return x[p].s <= Max && x[p].s >= Min;36 }37 38 int main(){39 scanf("%d", &n);40 scanf("%d%d%d", &A, &B, &C);41 for (int i = 1; i <= n; ++i){42 scanf("%d%d", &x[i].h, &x[i].s); 43 x[i].sum = A * x[i].h + B * x[i].s;44 y[i] = x[i];45 }46 47 sort(x + 1, x + n + 1, cmp1);48 sort(y + 1, y + n + 1, cmp2);49 for (int i = 1; i <= n; ++i){50 Min = x[i].s, Max = Min + C / B;51 l = 0, r = 0, cnt = 0;52 for (int j = 1; j <= n; ++j){53 while (r < n && y[r + 1].sum <= A * x[j].h + B * x[i].s + C)54 ++r, cnt += check1(r);55 while (l < n && x[l + 1].h < x[j].h)56 ++l, cnt -= check2(l);57 ans = max(ans, cnt); 58 }59 }60 printf("%d\n", ans);61 return 0;62 }
BZOJ1071 [SCOI2007]组队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。