|
| Description
|
| 给出两个数字的集合，A,B分别从中挑选一个中把两个数相乘，这样可以得到另外一个集合C。请问一下集合C中第k大的数是多少？
|
| Input
|
| 多组测试数据 每组测试中，第一行输入两个整数m,n，k（0 < n,m,k<50）k的值不大于C中集合个数 第二行有m个数代表集合A中的元素 第三行有n个数代表集合B中的元素
|
| Output
|
| 对于每组测试数据输出一行，代表C中第k大的数
|
Map 是 c++的一个标准容器，它提供了很好一对一的关系，在一些程序中建立一个 map
可以起到事半功倍的效果，总结了一些 map 基本简单实用的操作！?
1,map 构造函数；?
map<string,int >mapstring; map<int,string >mapint;?
map<sring,char>mapstring; map< char,string>mapchar;?
map<char,int>mapchar; map<int,char >mapint; ?
2,map 添加数据；?
map<int,string> maplive; ?
1.maplive.insert(pair<int,string>(102,"aclive"));?
2.maplive.insert(map<int,string>::value_type(321,"hai"));?
3. maplive[112]="April";//map 中最简单最常用的插入添加！?
3,map 中元素的查找：?
find()函数返回一个迭代器指向键值为 key 的元素，如果没找到就返回指向 map 尾部
的迭代器。 ?
map<int,string >::iterator l_it;; ?
l_it=maplive.find(112);?
if(l_it==maplive.end())?
cout<<"we do not find 112"<<endl;?
else cout<<"wo find 112"<<endl; ?
4,map 中元素的删除：?
如果删除 112；?
map<int,string >::iterator l_it;;?
l_it=maplive.find(112);?
if(l_it==maplive.end())?
cout<<"we do not find 112"<<endl;?
else maplive.erase(l_it); //delete 112;
5.map 的基本操作函数：?
C++ Maps 是一种关联式容器，包含“关键字/值”对?
begin() 返回指向 map 头部的迭代器?
clear(） 删除所有元素?
count() 返回指定元素出现的次数?
empty() 如果 map 为空则返回 true?
end() 返回指向 map 末尾的迭代器?
equal_range() 返回特殊条目的迭代器对?
erase() 删除一个元素?
find() 查找一个元素?
get_allocator() 返回 map 的配置器?
insert() 插入元素?
key_comp() 返回比较元素 key 的函数?
lower_bound() 返回键值>=给定元素的第一个位置?
max_size() 返回可以容纳的最大元素个数?
rbegin() 返回一个指向 map 尾部的逆向迭代器?
rend() 返回一个指向 map 头部的逆向迭代器?
size() 返回 map 中元素的个数?
swap() 交换两个 map?
upper_bound() 返回键值>给定元素的第一个位置?
value_comp() 返回比较元素 value 的函数?
本题分析：
题中描述有A，B两个集合，首先，先是输入AB两个集合的元素，再从AB中任意两个元素相乘后的结果保存到Map容器中，在经过一轮的排序之后，因为本身Map就有“去重”的功能，所以在最后直接输出第K大的数即可；
代码解析如下：
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int cmp(const void *a,const void *b) {
? ? return *(int *)b - *(int *)a;
}
int a[2510];
int main() {
? ? int m,n,k,i,j,temp;
? ? int x[55],y[55];
? ? map <int,int> mp;
? ? while(~scanf("%d%d%d",&m,&n,&k)) {
? ? ? ? mp.clear();
? ? ? ? for(i = 0; i < m; i++) {
? ? ? ? ? ? scanf("%d",&x[i]);
? ? ? ? }
? ? ? ? for(i = 0; i < n; i++) {
? ? ? ? ? ? scanf("%d",&y[i]);
? ? ? ? }
? ? ? ? temp = 0;
? ? ? ? for(i = 0; i < m; i++) {
? ? ? ? ? ? for(j = 0; j < n; j++) {
? ? ? ? ? ? ? ? if(!mp[x[i]*y[j]]) {
? ? ? ? ? ? ? ? ? ? mp[x[i]*y[j]]++;
? ? ? ? ? ? ? ? ? ? a[temp] = x[i] * y[j];
? ? ? ? ? ? ? ? ? ? temp++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? qsort(a,temp,sizeof(a[0]),cmp);
? ? ? ? printf("%dn",a[k-1]);
? ? }
}
后续解法待续。。。如有错误，敬请指正！
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
