首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。