uva 10763 Foreign Exchange(排序+二分查找)

2023-12-19 21:08

本文主要是介绍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(排序+二分查找)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/513695

相关文章

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

SQL 外键Foreign Key全解析

《SQL外键ForeignKey全解析》外键是数据库表中的一列(或一组列),用于​​建立两个表之间的关联关系​​,外键的值必须匹配另一个表的主键(PrimaryKey)或唯一约束(UniqueCo... 目录1. 什么是外键?​​ ​​​​2. 外键的语法​​​​3. 外键的约束行为​​​​4. 多列外键​

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常