1071: [SCOI2007]组队
https://lydsy.com/JudgeOnline/problem.php?id=1071
分析：
dp+单调性。
A*(hi–minH)+B*(si–minV)<=C
Ahi+Bsi<=C+A*minH+B*minV
如果枚举一个minH，和一个minV的话，那么把数组按Ahi+Bsi排序后，这个数组就具有单调性了。
这里面的人不一定满足si>=minV和hi>=minH。先固定一个minV，然后把所有大于等于minV的取出来。这样满足了第一个限制。然后枚举minH的时候会由于minH的增加而导致小于了minH，可以把所有加入的放进小根堆里，然后不断弹出不合法的。这样复杂度是$n^2logn$在bzoj上过不了的（luogu上开O2可以过）
考虑枚举的时候先si>=minV，那么就有A*(hi-minH)<=C+B*minV-B*si，因为要hi>=minH，所0<=左式<=右式，所以C+B*minV-B*si>=0，得到si<=C/B+mv，注意这样还没有满足左式>=0的条件，但是目前si应该满足minV<=si<=C/B+minV。
这样依然没有满足左式>=0的条件。考虑减去这些不合法的。这里只需要按h从i小到大的扫描所有人，如果这个si是合法的，那么减去。
这样减是否会减到一些没有枚举过的？
就是枚举下面的序列的时候，是否枚举到上面的排列的后面去。
是不会的。
下面序列的满足，hi<=minH，si<=C/B+minV，所以A*hi+B*si最大是A*minH+B*minV+C，刚好到第一个序列的位置。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ; struct Node{
int h, v; LL tot;
}s[N], mv[N], mh[N]; bool cmp1(const Node &A, const Node &B) {
return A.tot < B.tot;
}
bool cmp2(const Node &A, const Node &B) {
return A.h < B.h;
}
bool cmp3(const Node &A, const Node &B) {
return A.v < B.v;
} int main() {
int n = read(); LL A = read(), B = read(), C = read();
for (int i = ; i <= n; ++i) {
s[i].h = read(), s[i].v = read(); s[i].tot = A * s[i].h + B * s[i].v;
mv[i] = mh[i] = s[i];
}
sort(s + , s + n + , cmp1);
sort(mh + , mh + n + , cmp2);
sort(mv + , mv + n + , cmp3); int ans = ;
for (int i = ; i <= n; ++i) {
int p1 = , p2 = , cnt = ;
LL minv = mv[i].v, limv = minv + C / B;
for (int j = ; j <= n; ++j) {
LL minh = mh[j].h, limtot = C + A * minh + B * minv;
while (p1 <= n && s[p1].tot <= limtot) {
if (s[p1].v >= minv && s[p1].v <= limv) cnt ++;
p1 ++;
}
while (p2 <= n && mh[p2].h < minh) {
if (mh[p2].v >= minv && mh[p2].v <= limv) cnt --;
p2 ++;
}
ans = max(ans, cnt);
}
}
cout << ans;
return ;
}
线性
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ; struct Node{
int h, v; LL tot;
}s[N], mv[N], mh[N]; bool cmp1(const Node &A, const Node &B) {
return A.tot < B.tot;
}
bool cmp2(const Node &A, const Node &B) {
return A.h < B.h;
}
bool cmp3(const Node &A, const Node &B) {
return A.v < B.v;
}
priority_queue<int, vector<int>, greater<int> > q;
int main() {
int n = read(); LL A = read(), B = read(), C = read();
for (int i = ; i <= n; ++i) {
s[i].h = read(), s[i].v = read(); s[i].tot = A * s[i].h + B * s[i].v;
mv[i] = mh[i] = s[i];
}
sort(s + , s + n + , cmp1);
sort(mh + , mh + n + , cmp2);
sort(mv + , mv + n + , cmp3); int ans = ;
for (int i = ; i <= n; ++i) {
int p = , cnt = ;
LL minv = mv[i].v;
for (int j = ; j <= n; ++j) {
LL minh = mh[j].h, limtot = C + A * minh + B * minv;
while (p <= n && s[p].tot <= limtot) {
if (s[p].v >= minv && s[p].h >= minh) cnt ++, q.push(s[p].h);
p ++;
}
while (!q.empty() && q.top() < minh) cnt--, q.pop();
ans = max(ans, cnt);
}
}
cout << ans;
return ;
}
堆