题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1071
题目很好，居然写了很久，题解找了真多；
主要两种做法：
O(n^2lgn),通过优先堆维护，首先 等式变换：A*height+B*speed-C<=A*minheight+B*minspeed;
增加a[i].val=A*height+B*speed-C:
对a按height排序；
然后枚举i 把a[i].s作为min
/* ***********************************************
Author :forgot93
Created Time :2014/12/23 星期二 上午 9:00:41
File Name :
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <stdlib.h>
#include <time.h>
using namespace std; #define N 5555
typedef long long ll;
priority_queue<ll> q; struct node
{
ll h,s;
ll val;
bool operator < (const node &b) const{
return h>b.h;
}
}a[N]; int main()
{
int n;
ll A,B,C;
cin>>n>>A>>B>>C;
for (int i=;i<=n;i++){
cin>>a[i].h>>a[i].s;
a[i].val=A*a[i].h+B*a[i].s-C;
}
ll ans=;
sort(a+,a+n+); for (int i=;i<=n;i++)
{
ll minh=a[i].h;
ll mins=a[i].s;
while (!q.empty()) q.pop();
q.push(a[i].val);
for (int j=;j<=n;j++)
if (j!=i&&a[j].s>=mins)
{
minh=min(minh,a[j].h);
ll tmp=B*mins+A*minh;
if (a[i].val>tmp) break;
while (!q.empty()&&q.top()>tmp) q.pop();
if (a[j].val<=tmp)
{
q.push(a[j].val);
ans=max(ans,(ll) q.size());
}
}
}
cout<<ans<<endl;
return ;
}
speed;
接着暂时minheight=a[i].h;
a[i].h 是从大到小排序的；
接下来维护堆，我们枚举j 对于j!=i且a[j].s>=mins,
同时更新minheight;
然后把val满足的压入堆中；
对q.top()>val q.pop();
因为mins固定，minh是单调递减的所以前面满足的后面也会满足（这里请仔细考虑）；
时间是1100ms;
第二种是o(n*n);
时间是848ms;
关键字：单调；
/* ***********************************************
Author :forgot93
Created Time :2014/12/23 ÐÇÆÚ¶þ ÏÂÎç 2:46:36
File Name :c.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; typedef long long ll;
#define N 5555
struct node
{
int h,v;
ll val;
}H[N],V[N],a[N],r[N]; int cmp1(node x,node y)
{
if (x.h==y.h) return x.v<y.v;
return x.h<y.h;
}
int cmp2(node x,node y)
{
if (x.v==y.v) return x.h<y.h;
return x.v<y.v;
} int cmp3(node x,node y)
{
return x.val<y.val;
} int main()
{
int n;
ll A,B,C;
cin>>n>>A>>B>>C;
for (int i=;i<n;i++){
cin>>a[i].h>>a[i].v;
a[i].val=A*a[i].h+B*a[i].v-C;
H[i]=V[i]=a[i];
}
sort(a,a+n,cmp3);
sort(V,V+n,cmp2);
sort(H,H+n,cmp1);
int ans=;
for (int i=;i<n;i++)
{
int minh=H[i].h,p=,cnt=,tot=;
for (int j=;j<n;j++)
if (V[j].h>=minh&&V[j].v<=H[i].v)
r[tot++]=V[j];
for (int j=;j<tot;j++)
{
int minv=r[j].v;
ll res=A*minh+B*minv;
while (p<n&&a[p].val<=res)
{
if (a[p].h<minh||a[p].v<minv) cnt++;
p++;
}
ans=max(p-cnt,ans);
if (res>=A*r[j].h+B*r[j].v-C) cnt++;
if (p==n) break;
}
}
printf("%d\n",ans);
return ;
}
首先 按照某些关键字排序。
for i minh=a[i].h;
然后枚举 j 寻找mins,mins<a[i],s;
然后是单调队列；
有这样一个性质：我们枚举指针的时候是按val 从小到大拍好顺序的，我们枚举的mins也是从小到大的，所以：
（这里） 前面的元素一定满足后面的，怎么理解？
枚举的mins2能够满足mins1的所有元素，所以指针p不必归0了。
所以就会O(n^2);