[SCOI2007]组队差分

题面：[SCOI2007]组队

题解：

　　一开始固定H然后找性质找了很久也没有找到任何有用的东西。。。。。。

　　然后大佬告诉我一个神奇的方法。。。

　　首先我们化一波式子：

　　设$H$表示高度的最小值，$V$表示速度的最小值

　　$$A(h[i] - H) - B(v[i] - V) le C$$
　　$$Ah[i] - AH + Bv[i] - BV le C$$　　

　　如果我们枚举$h[i]$,那么$h[i]$就可以被当做一个常量，于是我们把常量都放在一起。
　　设$$S_{i} = Ah[i] - AH - C$$
　　则$$S_{i} + BV[i] - BV le 0$$
　　$$S_{i} + BV[i] <= BV$$
　　$$frac{S_{i}}{B} + V[i] le V le V[i]$$

　　最后那个$le V[i]$是因为V是最小值.

　　于是我们可以发现，在固定H的情况下，对于任意一个V[i],它可以对在$[frac{S_{i}}{B} + V[i], V[i]]$之间的V产生贡献。

　　于是对于每个固定的H，我们的最大答案就看V最大能被多少个点产生贡献。

　　差分维护即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 5500
 5 #define ac 101000
 6 #define LL long long
 7 
 8 int n, ans, maxn, d[ac];
 9 int A, B, C;
10 
11 struct node{
12     int h, v;
13     friend bool operator < (const node &a, const node &b){return a.h < b.h;}
14 }s[AC];
15 
16 inline int read()
17 {
18     int x = 0;char c = getchar();
19     while(c > '9' || c < '0') c = getchar();
20     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
21     return x;
22 }
23 
24 inline void upmax(int &a, int b){
25     if(b > a) a = b;
26 }
27 
28 inline void pre()
29 {
30     n = read(), A = read(), B = read(), C = read();
31     for(R i = 1; i <= n; i ++) 
32     {
33         s[i].h = read(), s[i].v = read();
34         upmax(maxn, s[i].v);
35     }
36     sort(s + 1, s + n + 1);
37 }
38 
39 void work()
40 {
41     for(R i = 1; i <= n; i ++)//枚举minh
42     {
43         int H = s[i].h, all = H * A;
44         for(R j = i; j <= n; j ++)//在h符合条件的点当中选点来更新minv
45         {
46             int l = (s[j].h * A - all - C) / B + s[j].v, r = s[j].v;
47             if(l <= 0) l = 1;
48             if(l > r) continue;
49             ++ d[l], -- d[r + 1];
50         }
51         int tmp = 0;
52         for(R j = 1; j <= maxn; j ++)
53             tmp += d[j], upmax(ans, tmp), d[j] = 0;
54     }
55     printf("%d
", ans);
56 }
57 
58 int main()
59 {
60     freopen("in.in", "r", stdin);
61     pre();
62     work();
63     fclose(stdin);
64     return 0;
65 }

View Code

　　不知道为什么卡不过大佬QAQ。。。

[SCOI2007]组队 差分

[SCOI2007]组队差分