首页 > 代码库 > poj1442（Black Box）

poj1442（Black Box）

2024-07-14 11:46:21   214人阅读

题目地址：Black Box

 

题目大意：

    有一个黑盒子可以进行两种操作,一种是ADD往盒子里存数，一种是GET查找盒子里的第几个数，默认盒子里始终是从小到大排列，然后A（1）、A（2）....A（M）为要存进盒子的数，u（1）、u（2）、....u（N）的数并不是取出第几个数，而这里u（N）存的数是插入几个A（M）到盒子里去，这里有一个P(1 <= p <= N) 和u是同序列的。输出 p-minimum number from our A(1), A(2), ..., A(u(p)) sequence.  p从1开始到N ，p为多少输出第几小的数。

 

解题思路 ：

    首先每次循环用到sort超时。

代码：

 1 const int M=30005; 2 int s2[M],s1[M],s3[M]; 3 int main() 4 { 5     int m,n; 6     priority_queue<int >Q; 7     while(scanf("%d%d",&m,&n)!=EOF) 8     { 9         memset(s1,0,sizeof(s1));10         memset(s2,0,sizeof(s2));11         int i,j,k;12         for(i=1;i<=m;i++)13             scanf("%d",&s1[i]);14         int d=1;15         int cnt=0;16         for(i=1;i<=n;i++)17         {18             scanf("%d",&s2[i]);19             for(j=d;j<=s2[i];j++)20             {21                 d=j+1;22                 s3[++cnt]=s1[j];23             }24             sort(s3,s3+cnt+1);25             printf("%d\n",s3[i]);26         }27     }28     return 0;29 }
View Code

sort最坏的时间复杂度是n*n,一般是nlog(n).所以每次循环用的很费时。

而优先队列的时间复杂度最坏log（n）。

首先用优先队列分别建立一个最小堆和一个最大堆，让最大堆始终存储前p小个数，所以最大堆的堆顶就是题目要求的get。最小堆始终存储剩余的数。关键是怎么往最大、和最小堆push。当p=1时。Q2为空，直接全都push最最小堆Q1里，最后将最小堆的堆顶Q1.top（）传给最大推Q2。这时Q2里有一个数，当p=2时，需要push到Q1时每次比较如果有小于Q2.top（），然后将最大最小堆栈顶交换，最后再将最小堆的堆顶Q1.top（）传给最大推Q2，以此类推. . .这样就保证了Q2始终存的是前P小个数。

代码：

 1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 //#include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 /***************************************/21 const int INF = 0x7f7f7f7f;22 const double eps = 1e-8;23 const double PIE=acos(-1.0);24 const int d1x[]= {0,-1,0,1};25 const int d1y[]= {-1,0,1,0};26 const int d2x[]= {0,-1,0,1};27 const int d2y[]= {1,0,-1,0};28 const int fx[]= {-1,-1,-1,0,0,1,1,1};29 const int fy[]= {-1,0,1,-1,1,-1,0,1};30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/31 /***************************************/32 void openfile()33 {34     freopen("data.in","rb",stdin);35     freopen("data.out","wb",stdout);36 }37 priority_queue<int> qi1;38 priority_queue<int, vector<int>, greater<int> >qi2;39 /**********************华丽丽的分割线,以上为模板部分*****************/40 const int M=30005;41 int s1[M],s2[M];42 int main()43 {44     int m,n;45     priority_queue<int >Q2;46     priority_queue<int ,vector<int>,greater<int> >Q1;47     while(scanf("%d%d",&m,&n)!=EOF)48     {49         memset(s1,0,sizeof(s1));50         memset(s2,0,sizeof(s2));51         int i,j,k;52         for(i=1;i<=m;i++)53             scanf("%d",&s1[i]);54         int d=1;55         for(i=1;i<=n;i++)56         {57             scanf("%d",&s2[i]);58             for(j=d;j<=s2[i];j++)59             {60                 d=j+1;61                 Q1.push(s1[j]);62                 if (!Q2.empty()&&Q1.top()<Q2.top())63                 {64                     int v1=Q1.top();65                     int v2=Q2.top();66                     Q1.pop();67                     Q1.push(v2);68                     Q2.pop();69                     Q2.push(v1);70                 }71             }72             int v=Q1.top();73             Q2.push(v);74             Q1.pop();75             printf("%d\n",Q2.top());76         }77     }78     return 0;79 }
View Code

 


联系
我们