本文主要是介绍uva 10763 Foreign Exchange（排序+二分查找），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是我第一次算出来应该用什么复杂度写的题，或许是这一章刚介绍过，500000的数据必须用nlogn，所以我就
想到了二分，它的复杂度是logn，再对n个数据进行遍历，正好是nlogn，前两次TLE了，然后我就对我的做法没信心
了。。。看到一篇博客上说就应该这种方法，然后我就坚定的改自己的算法去了，哈哈，专注度没有达到五颗星，最多
三颗。。。
思路：
我用的是结构体保存的，先对每一对序列排序，然后对第二个元素在第一个元素中二分搜索，用到了
lower_bound，upper_bound，注释里面有写它的功能，其实这两个可以直接调用的。。。注意一下用
upper_bound的时候最后一个元素就ok啦。。。TLE其实不是我的算法的事，而是因为我把这两个函数写到循环里面
了，真傻。。。这样每次循环都会调用的。。。看网上有人说最后套数据n是小于1000的，加个if（n>1000）
for(;;;)就可以啦，哈哈，真聪明，我学会了。。。以后试着用一下。。
贴代码：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct node
{int i,j;
}a[500005];
int visit[500005];//用来标记是否已经配对过了
int n;
int cmp(const void *a,const void *b)//结构体的二级排序
{if(((node *)a)->i != ((node *)b)->i)return ((node *)a)->i - ((node *)b)->i;return ((node *)a)->j - ((node *)b)->j;
}
int lower_bound(int v)//二分查找，如果要查找的值存在的话，返回第一个等于该元素的位置，否则返回一个它要插入的第一个位置（序列必须先排序）
{int m,x = 1,y = n;while(x < y ){m = x + (y-x)/2;if(a[m].i >= v) y = m ;elsex = m + 1;}return x;
}
int upper_bound(int v)//二分查找，如果存在该元素，就返回它的下一个位置（最后一个除外，就是说如果最后一个元素等于v,就返回的是n），如果不存在，就返回它插入后仍有序的序列
{int m;int x = 1;int y = n;while(x < y){m = x +(y -x)/2;if(a[m].i<=v) x = m+1;elsey = m;}return x;
}
int main()
{int i,j;while(cin >> n, n){memset(visit,0,sizeof(visit));for(i=1; i<=n; i++){// cin >> a[i].i >> a[i].j;//cin输入流比较费时 scanf("%d%d",&a[i].i,&a[i].j);}qsort(a+1,n,sizeof(a[0]),cmp);// for(i=1; i<=n; i++)// {//cin >> a[i].i >> a[i].j;// scanf("%d%d",&a[i].i,&a[i].j);// cout << a[i].i << " "<< a[i].j << endl;// }int flag1 = 0;for(i=1; i<=n; i++){if(visit[i] == 1)//配对过的不再访问 continue;int flag = 0;int first = lower_bound(a[i].j);int last = upper_bound(a[i].j);// cout << "first = " << first << " " << last << endl;if(a[first].i != a[i].j)//没有与之配对的直接退出输出NO {flag1 =1;break;}if(last == n)//把n的情况特判一下 last ++;for(j=first; j<last; j++){if(visit[j] == 1)continue;if(a[j].j == a[i].i){visit[j] = 1;flag = 1;break;}}if(!flag){flag1 = 1;break;}visit[i] = 1;}if(flag1)cout << "NO" << endl;// puts("NO");elsecout << "YES" << endl;//puts("YES");} return 0;
}
这篇关于uva 10763 Foreign Exchange（排序+二分查找）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
