学步园

The Frog's Games

二分枚举答案

#include<iostream>
#include<algorithm>
using namespace std;
int L,n,m;
int a[500002];
int cmp(const void *c ,const void *b ) 
{ 
return *(int *)c - *(int *)b; 
} 
int main()
{
while(scanf("%d %d %d",&L,&n,&m)==3)
    {
int maxn=0;
for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        a[0]=0;a[n+1]=L;
if(n==0) {printf("%d\n",L);continue;}
        qsort(a,n+2,sizeof(a[0]),cmp);
int left=L/m,right=L,count,flag;
while(left<=right)
        {
int mid=(left+right)/2;
            count=flag=0;
for(int i=1;i<=n+1;)
            {
if(a[i]-a[i-1]>mid)
                {
                    flag=1;break;
                }
int temp=i-1;
while(a[i]-a[temp]<=mid)
                    i++;
                count++;
if(count>m) {flag=1;break;}
            }
if(flag) left=mid+1;
else right=mid-1;
        }
        printf("%d\n",left);
    }
return 0;
}

 

 

The kth great number

利用优先队列，每次只保存前K大个数，操作很简单

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int main()
{
int n,k,b;
char str[2];
while(scanf("%d %d",&n,&k)==2)
    {
        priority_queue<int,vector<int>,greater<int> > Q;
while(n--)
    {
        scanf("%s",str);
if(str[0]=='I')
        {
            scanf("%d",&b);
            Q.push(b);
if(Q.size()>k)
          { Q.pop();}
        }
else printf("%d\n",Q.top());
    }
    }
return 0;
}