首页 > 代码库 > PAT-1048 Find Coins (25)

PAT-1048 Find Coins (25)

这道题目需要用二分查找,否则可能超时,时间复杂度应嘎是n.lgn。可以通过。

二分查找末班

int find(l,r)

{

   int mid=(l+r)/2;

   if(data[mid]==num)

         return mid;

   else if ...

        return find(l,mid-1) //注意是return find(l,mid-1)而不是find(l,mid-1)否则返回值会丢掉。

   else

       return find(mid+1,r)

}

// 1048.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<iostream>#include<algorithm>using namespace std;#define MIN(a,b) a>b?b:a#define MAX(a,b) a>b?a:b#define max 100010int data[max];bool find(int l,int r,int d,int index) //二分查找需要return find(l,mid+1,...) 而不是直接调用{    if(l>r)        return false;    int mid=(l+r)/2;    if(data[mid]==d)    {        if(mid!=index)           return true;        else //如果有多个Mid值得话,排序之后肯定是在一块的        {            if(data[mid+1]==d||data[mid-1]==d)                return true;            else                return false;        }    }    else if(data[mid]>d)    {        return find(l,mid-1,d,index);    }    else if(data[mid]<d)    {        return find(mid+1,r,d,index);    }    return false;}int main(){   int n,m;   freopen("1048.txt","r",stdin);   while(scanf("%d%d",&n,&m)!=EOF)   {       for(int i=0;i<n;i++)       {           scanf("%d",&data[i]);       }       sort(data,data+n);       bool flag=false;       for(int i=0;i<n;i++)       {           int tmp=m-data[i];           flag=find(0,n-1,tmp,i);           if(flag)           {              printf("%d %d\n",MIN(data[i],tmp),MAX(data[i],tmp));              break;           }       }       if(!flag)       {           printf("No Solution\n");       }   }    return 0;}

 

PAT-1048 Find Coins (25)