第十二周测验

偏执的太偏执、 2022-05-14 08:51 297阅读 0赞

10687 sort 简单题 http://cxsjsxmooc.openjudge.cn/2016hw12/1/

10688 还是 sort 简单题 http://cxsjsxmooc.openjudge.cn/2016hw12/2/

10689 点集的查询 http://cxsjsxmooc.openjudge.cn/2016hw12/3/

3341 Set http://cxsjsxmooc.openjudge.cn/2016hw12/4/

3343 热血格斗场 http://cxsjsxmooc.openjudge.cn/2016hw12/5/

## 3344:冷血格斗场 ##

## 1:sort简单题 ##

描述

程序填空，产生指定输出结果

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
    	int a[8] = {6,5,14,23,2,9,87,10 };
    	sort(

// 在此处补充你的代码

);
    	for(int i = 0;i < 8; ++i)
    		cout << a[i] << "," ; 
    	return 0;
    }

输入

无

输出

6,87,23,14,9,5,2,10,  
  
提示：除第一个和最后一个数外，其他都从大到小排序

样例输入

无

样例输出

6,87,23,14,9,5,2,10,

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
    	int a[8] = {6,5,14,23,2,9,87,10 };
    	sort(a+1,a+7,greater<int>()); 
    	for(int i = 0;i < 8; ++i)
    		cout << a[i] << "," ; 
    	return 0;
    }

### 2:还是sort简单题 ###

描述

程序填空，产生指定输出结果

#include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    struct Point{
    	int x;
    	int y;
    };

// 在此处补充你的代码

int main()
    {
    	int a[8] = {6,5,55,23,3,9,87,10 };
    	sort(a,a+8,Rule1());
    	for(int i = 0;i < 8; ++i)
    		cout << a[i] << "," ; 
    	cout << endl;
    	Point ps[8] = {
       {1,0},{0,1},{0,-1},{-1,0},{1,-1},{1,1},{2,0},{-2,0} } ;
    	sort(ps,ps+8,Rule2());
    	for(int i = 0;i < 8; ++i)
    		cout << "(" << ps[i].x << "," << ps[i].y << ")"; 
    	return 0;
    }

输入

无

输出

10,23,3,55,5,6,87,9,  
(-1,0)(0,-1)(0,1)(1,0)(1,-1)(1,1)(-2,0)(2,0)  
  
整数按照个位数从小到大排。个位数相同，则大的排前面  
  
点按照离原点从近到远排。距离相同，则按x坐标从小到大排。x坐标也相同，则按y坐标从小到大排

样例输入

无

样例输出

10,23,3,55,5,6,87,9,
    (-1,0)(0,-1)(0,1)(1,0)(1,-1)(1,1)(-2,0)(2,0)

#include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    struct Point{
    	int x;
    	int y;
    };
    // 在此处补充你的代码
    struct Rule1{
    	bool operator()(const int &a1, const int &a2)
    	{
    		if(a1%10 != a2%10)
    			return a1%10 < a2%10;
    		else
    			return a1 > a2;
    	}
    };
    
    struct Rule2{
    	bool operator()(const Point &a1, const Point &a2)
    	{
    		double a = sqrt(pow(a1.x,2) + pow(a1.y,2));
    		double b = sqrt(pow(a2.x,2) + pow(a2.y,2));
    		if(a != b)
    			return a < b;
    		else if(a1.x != a2.x)
    			return a1.x < a2.x;
    		else
    			return a1.y < a2.y;
    	}
    };
    int main()
    {
    	int a[8] = {6,5,55,23,3,9,87,10 };
    	sort(a,a+8,Rule1());
    	for(int i = 0;i < 8; ++i)
    		cout << a[i] << "," ; 
    	cout << endl;
    	Point ps[8] = {
       {1,0},{0,1},{0,-1},{-1,0},{1,-1},{1,1},{2,0},{-2,0} } ;
    	sort(ps,ps+8,Rule2());
    	for(int i = 0;i < 8; ++i)
    		cout << "(" << ps[i].x << "," << ps[i].y << ")"; 
    	return 0;
    }

参考答案：

#include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    struct Point{
    	int x;
    	int y;
    };
    // 在此处补充你的代码
    struct Rule1{
    	bool operator()(const int &a1, const int &a2)
    	{
    		if(a1%10 != a2%10)
    			return a1%10 < a2%10;
    		else
    			return a1 > a2;
    	}
    };
    
    double distance(Point p)
    {
    	return sqrt(p.x*p.x+p.y*p.y);
    }
    
    struct Rule2{
    	bool operator()(const Point &a1, const Point &a2)
    	{
    		if(abs(distance(a1)-distance(a2)) < 1e-7)//相当于距离相等 
    		{
    			if(a1.x != a2.x)
    				return a1.x < a2.x;
    			else
    				return a1.y < a2.y;
    		}
    		else
    			return distance(a1) < distance(a2);
    	}
    };
    int main()
    {
    	int a[8] = {6,5,55,23,3,9,87,10 };
    	sort(a,a+8,Rule1());
    	for(int i = 0;i < 8; ++i)
    		cout << a[i] << "," ; 
    	cout << endl;
    	Point ps[8] = {
       {1,0},{0,1},{0,-1},{-1,0},{1,-1},{1,1},{2,0},{-2,0} } ;
    	sort(ps,ps+8,Rule2());
    	for(int i = 0;i < 8; ++i)
    		cout << "(" << ps[i].x << "," << ps[i].y << ")"; 
    	return 0;
    }

## 3:Set ##

描述

现有一整数集（允许有重复元素），初始为空。我们定义如下操作：  
add x 把x加入集合  
del x 把集合中所有与x相等的元素删除  
ask x 对集合中元素x的情况询问  
对每种操作，我们要求进行如下输出。  
add 输出操作后集合中x的个数  
del 输出操作前集合中x的个数  
ask 先输出0或1表示x是否曾被加入集合（0表示不曾加入），再输出当前集合中x的个数，中间用空格格开。

输入

第一行是一个整数n，表示命令数。0<=n<=100000。  
后面n行命令，如Description中所述。

输出

共n行，每行按要求输出。

样例输入

7
    add 1
    add 1
    ask 1
    ask 2
    del 2
    del 1
    ask 1

样例输出

1
    2
    1 2
    0 0
    0
    2
    1 0

提示

Please use STL’s set and multiset to finish the task

> 这里需要注意一个概念，用erase(s)时，multiset中所有的s元素都会删除，而不是只删除一个。

#include<iostream>
    #include<set>
    using namespace std;
    int main()
    {
    	multiset<int> st;
    	st.insert(2);
    	st.insert(7);
    	st.insert(3);
    	st.insert(4);
    	st.insert(3);
    	st.insert(2);
    	st.insert(2);
    	multiset<int>::iterator p;
    	for(p = st.begin(); p != st.end(); ++p)
    	{
    		cout << *p << " ";
    	}
    	cout << endl;
    	st.erase(2);//删除st中的元素2，是将所有的2都删除，而不是只删除一个 
    	cout << st.count(2) << endl;//0
    	cout << st.count(3) << endl;//2
    	return 0;
    }

![70][]

本题代码：

#include<iostream>
    #include<set>
    #include<string>
    #include<cstring>
    using namespace std;
    
    multiset<int> st1;
    set<int> st2;
    
    int main()
    {
    	char ch[5];
    	int n,num;
    	cin >> n;
    	while(n--)
    	{
    		cin >> ch >> num;
    		switch(ch[1])
    		{
    			case 'd':
    				st1.insert(num);
    				st2.insert(num);
    				cout << st1.count(num) << endl;
    				break;
    			case 'e':
    				cout << st1.count(num) << endl;
    				st1.erase(num);
    				break;
    			case 's':
    				if(st2.find(num) == st2.end())//st2.find(num)可以用来查找num是否加入过集合 
    					cout << "0 0" << endl;
    				else
    				{
    					cout << "1 " << st1.count(num) << endl;
    				}
    				break;
    		}
    	}
    	return 0;
    }

参考代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<set>
    using namespace std;
    typedef multiset<int>::iterator PTR;
    int main()
    {
    	int n;
    	multiset<int> mst;
    	set<int> st;
    	PTR p;
    	scanf("%d",&n);
    	for(int i = 0; i < n; ++i)
    	{
    		char cmd[20];
    		int x;
    		scanf("%s%d",cmd,&x);
    		switch(cmd[1])
    		{
    			case 'd':
    				st.insert(x);
    				mst.insert(x);
    				printf("%d\n",mst.count(x));
    				break;
    			case 'e':
    				printf("%d\n",mst.count(x));
    				p = mst.find(x);
    				if(p != mst.end())//找到有几个x，将这几个x都删掉 
    				{
    					pair<PTR,PTR> range = mst.equal_range(x);
    					mst.erase(range.first,range.second);
    				}
    				break;
    			case 's':
    				set<int>::iterator pp = st.find(x);
    				if(pp != st.end())
    					printf("1 %d\n",mst.count(x));
    				else
    					printf("0 %d\n",mst.count(x));
    				break;
    		}
    	}
    	
    }

## 4:热血格斗场 ##

描述

为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个（显然，虐人必被虐好）。

不幸的是，Facer一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录，按照时间顺序依次输出每场比赛双方的id。

输入

第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。输入保证两人的实力值不同。

输出

N行，每行两个数，为每场比赛双方的id，新手的id写在前面。

样例输入

3
    2 1
    3 3
    4 2

样例输出

2 1
    3 2
    4 2

> 这里需要明确st.end()是指向的最后一个数下一个数的位置，还有lower\_bound(K)指>=K的数的位置，upper\_bound(K)指>K的位置。具体使用方法可以看看下面这个代码。

#include<iostream>
    #include<set>
    using namespace std;
    int main()
    {
    	set<int>st;
    	st.insert(7);
    	st.insert(9);
    	st.insert(4);
    	st.insert(8);
    	set<int>::iterator p1;
    	p1 = st.lower_bound(9);
    	cout << *p1 << endl;//9
    	set<int>::iterator p2;
    	p2 = st.upper_bound(8);
    	cout << *p2 << endl;//9
    	cout << * (-- st.end() )<< endl;//9
     	return 0;
    }

> 【思路】本题需要新来的与老队员相比，老队员可以存储在set中，按照实力自动排序，让新来的数的实力与set中的相比，有三种情况：都比set中的数大，都比set中的数小，介于两者之间。
> 
> 新数比set中的所有数大时，输出新数和set中最后一个数的id。
> 
> 新数比set中的所有数小时，输出新数和set中第一个数的id。
> 
> 如果介于两者之间，那么比较新数和他前后的数比较，看谁的差值比较小。
> 
> 用结构体中的id记录编号

#include<iostream>
    #include<set>
    #include<cstdio>
    using namespace std;
    
    struct Fighter{
    	int id;
    	int power;
    }; 
    
    struct Rule{
    	bool operator()(const Fighter &f1, const Fighter &f2)
    	{
    		return f1.power < f2.power;
    	}
    };
    
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	set<Fighter,Rule> st;
    	Fighter ft;
    	ft.id = 1;
    	ft.power = 1000000000;
    	st.insert(ft);
    	for(int i = 0; i < n; ++i)
    	{
    		scanf("%d%d",&ft.id,&ft.power);
    		set<Fighter>::iterator pl = st.lower_bound(ft);
    		set<Fighter>::iterator pu = st.upper_bound(ft);
    		if(pl == st.begin())//所有人的实力都比ft强 
    		{
    			printf("%d %d\n",ft.id,pl->id);
    		}
    		else if(pu == st.end())//所有人的实力都比ft弱,st.end()指向的是最后一个数的下一个数 
    		{
    			-- pu;
    			printf("%d %d\n",ft.id,pu->id);
    		}
    		else
    		{
    			--pl;
    			if(ft.power - pl->power <= pu->power - ft.power)
    				printf("%d %d\n",ft.id,pl->id);
    			else
    				printf("%d %d\n",ft.id,pu->id);
    		}
    		st.insert(ft);
    	} 
    	return 0;
    }

> 使用map的方法，要用printf和scanf进行输出输入。

#include<iostream>
    #include<map>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    map<int,int>mp;
    map<int,int>::iterator p;
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	int id,pw;
    	while(n--)
    	{
    		scanf("%d%d",&id,&pw);
    		mp[1000000000]=1;
    		p = mp.lower_bound(pw);
    		if(p == mp.end())//新队员实力最强 
    		{
    			--p;
    			printf("%d %d\n",id,p->second);
    		}
    		else if(p != mp.begin())//新队员实力界于中间 
    		{
    			int p1 = p->first - pw;//实力比新队员强但实力最相近的队员，或者实力相等的队员 
    			--p;
    			int p2 = pw - p->first;//实力比新队员弱的实力最相近的队员。或者实力相等的队员 
    			if(p1 == p2 || p1 > p2)//实力相等，选择弱的，或者选择实力相差不大的 
    				printf("%d %d\n",id,p->second);
    			else if(p1 < p2)
    			{
    				++p;
    				printf("%d %d\n",id,p->second);
    			}
    				
    		}
    		else//新队员实力最弱 
    			printf("%d %d\n",id,p->second);
    		mp[pw]=id;		
    	}
    	return 0;
    }

3344:冷血格斗场

描述

为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家冷血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值，两人的实力值可以相同。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有多个人的实力值与他差别相同，则他会选择id最小的那个。

输入

第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。

输出

N行，每行两个数，为每场比赛双方的id，新手的id写在前面。

样例输入

3
    2 3
    3 1
    4 2

样例输出

2 1
    3 2
    4 2

> 本题最好使用map,map<first,second>mp.可以用second记录id，用first比较大小。

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<algorithm>
    #include<map>
    using namespace std;
    map<int,int>mp;
    map<int,int>::iterator p;
    int n;
    int main()
    {
    	mp[1000000000] = 1;
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		int id,pw;
    		cin >> id >> pw;
    		p = mp.lower_bound(pw);
    		if(p == mp.end())//mp中所有的老会员的实力都比它弱 
    			p--;
    		int t = abs(p->first-pw),idx = p->second;
    		if(p != mp.begin()) //新来的会员实力处于中间水平，如果p==mp.begin()，说明新来的会员实力最弱 
    		{
    			p--;
    			if(t > abs(p->first-pw)||(t == abs(p->first-pw)&&p->second<idx))//比较和新会员能力值相邻的左右两个数的差值大小，选择差值小的比赛，如果差值相等，那选择id小的比赛 
    			{
    				t = abs(p->first-pw);
    				idx = p->second;
    			}
    		}
    		cout << id << " " << idx << endl;
    		p = mp.find(pw);
    		if(p == mp.end() || p->second > id)//原set中没有pw，或者有pw但是新输入的id比原来的会员的id小 
    		{
    			mp[pw] = id;
    		}
    	}
    	return 0;
    }

用这个会超时，输入输出用scanf和printf就对了。

#include<cstdio>
    #include<map>
    #include<algorithm> 
    #include<iostream>
    using namespace std;
    map<int,int>mp;
    map<int,int>::iterator p;
    int n;
    int main()
    {
    	mp[1000000000] = 1;
    	//cin >> n;
    	scanf("%d",&n);
    	for(int i = 1; i <= n; ++i)
    	{
    		int id,pw;
    		//cin >> id >> pw;
    		scanf("%d%d",&id,&pw);
    		p = mp.lower_bound(pw);
    		if(p == mp.end())//mp中所有的老会员的实力都比它弱 
    			p--;
    		int t = abs(p->first-pw),idx = p->second;
    		if(p != mp.begin()) //新来的会员实力处于中间水平，如果p==mp.begin()，说明新来的会员实力最弱 
    		{
    			p--;
    			if(t > abs(p->first-pw)||(t == abs(p->first-pw)&&p->second<idx))//比较和新会员能力值相邻的左右两个数的差值大小，选择差值小的比赛，如果差值相等，那选择id小的比赛 
    			{
    				t = abs(p->first-pw);
    				idx = p->second;
    			}
    		}
    	//	cout << id << " " << idx << endl;
    		printf("%d %d\n",id,idx);
    		p = mp.find(pw);
    		if(p == mp.end() || p->second > id)//原set中没有pw，或者有pw但是新输入的id比原来的会员的id小 
    		{
    			mp[pw] = id;
    		}
    	}
    	return 0;
    }

> 热血格斗场和冷血格斗场这两个题的区别是，热血格斗场如果能力差值相等，选择比自己弱的。冷血格斗场是如果能力差值相等，选择id小的。规则有区别。

[70]: /images/20220514/9a73c27e085242449026e7df27922002.png