首页 > 代码库 > BZOJ 1071组队

BZOJ 1071组队

 题目链接: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

技术分享
 1 /* *********************************************** 2 Author        :forgot93 3 Created Time  :2014/12/23 星期二 上午 9:00:41 4 File Name     : 5 ************************************************ */ 6  7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream>10 #include <algorithm>11 #include <vector>12 #include <queue>13 #include <set>14 #include <map>15 #include <string>16 #include <stdlib.h>17 #include <time.h>18 using namespace std;19 20 #define N 555521 typedef long long ll;22 priority_queue<ll> q;23 24 struct node25 {26     ll h,s;27     ll val;28     bool operator < (const node  &b) const{29     return h>b.h;30     }31 }a[N];32 33 34 int main()35 {36     int n;37     ll A,B,C;38     cin>>n>>A>>B>>C;39     for (int i=1;i<=n;i++){40     cin>>a[i].h>>a[i].s;41     a[i].val=A*a[i].h+B*a[i].s-C;42     }43     ll ans=1;44     sort(a+1,a+n+1);45     46     for (int i=1;i<=n;i++)47     {48         ll minh=a[i].h;49         ll mins=a[i].s;50         while (!q.empty()) q.pop();51         q.push(a[i].val);52         for (int j=1;j<=n;j++)53         if (j!=i&&a[j].s>=mins)54         {55             minh=min(minh,a[j].h);56             ll tmp=B*mins+A*minh;57             if (a[i].val>tmp) break;58             while (!q.empty()&&q.top()>tmp) q.pop();59             if (a[j].val<=tmp)60             {61                 q.push(a[j].val);62                 ans=max(ans,(ll) q.size());63             }64         }65     }66     cout<<ans<<endl;67     return 0;68 }
View Code

 

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;

关键字:单调;

技术分享
 1 /* *********************************************** 2 Author        :forgot93 3 Created Time  :2014/12/23 ÐÇÆÚ¶þ ÏÂÎç 2:46:36 4 File Name     :c.cpp 5 ************************************************ */ 6  7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream>10 #include <algorithm>11 #include <vector>12 #include <queue>13 #include <set>14 #include <map>15 #include <string>16 #include <math.h>17 #include <stdlib.h>18 #include <time.h>19 using namespace std;20 21 typedef long long ll;22 #define N 555523 struct node24 {25    int h,v;26    ll val;27 }H[N],V[N],a[N],r[N];28 29 int cmp1(node x,node y)30 {31     if (x.h==y.h) return x.v<y.v;32     return x.h<y.h;33 }34 int cmp2(node x,node y)35 {36     if (x.v==y.v) return x.h<y.h;37     return x.v<y.v;38 }39 40 int cmp3(node x,node y)41 {42     return x.val<y.val;43 }44 45 46 int main()47 {48     int n;49     ll A,B,C;50     cin>>n>>A>>B>>C;51     for (int i=0;i<n;i++){52     cin>>a[i].h>>a[i].v;53     a[i].val=A*a[i].h+B*a[i].v-C;54     H[i]=V[i]=a[i];55     }56     sort(a,a+n,cmp3);57     sort(V,V+n,cmp2);58     sort(H,H+n,cmp1);59     int ans=0;60     for (int i=0;i<n;i++)61     {62         int minh=H[i].h,p=0,cnt=0,tot=0;63         for (int j=0;j<n;j++)64         if (V[j].h>=minh&&V[j].v<=H[i].v)65             r[tot++]=V[j];66         for (int j=0;j<tot;j++)67         {68             int minv=r[j].v;69             ll res=A*minh+B*minv;70             while (p<n&&a[p].val<=res)71             {72                 if (a[p].h<minh||a[p].v<minv) cnt++;73                 p++;74             }75             ans=max(p-cnt,ans);76             if (res>=A*r[j].h+B*r[j].v-C) cnt++;77             if (p==n) break;78         }79     }80     printf("%d\n",ans);81     return 0;82 }
View Code 

首先 按照某些关键字排序。

for i minh=a[i].h;

然后枚举 j 寻找mins,mins<a[i],s;

然后是单调队列;

有这样一个性质:我们枚举指针的时候是按val 从小到大拍好顺序的,我们枚举的mins也是从小到大的,所以:

(这里) 前面的元素一定满足后面的,怎么理解?

枚举的mins2能够满足mins1的所有元素,所以指针p不必归0了。

所以就会O(n^2);

 

                                                        

BZOJ 1071组队