目录
热血格斗场
总时间限制:
1000ms
内存限制:
65536kB
描述
为了迎接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
思路:
1.会员结构体
我们可以编写一个会员的结构,里面有ID和实力值两个结构变量,以及一个初始化的构造函数,刚开始初始化为0
1.2结构体代码:
struct hy{ //定义一个会员
long long id; //会员的ID账号
long long s; //会员的实力值
hy(long long _id=0,long long _s=0){//构造函数初始化
id=_id; //赋值
s=_s; //赋值
}
};
2.输入
因为我们格斗场初始以及有一个会员了,所以现在的会员总数是n+1,所以我们可以定义一个长度为n+1的结构数组,然后输入的时候赋值就行了,因为题目给出了第一位会员的信息,我们在程序最开始的时候定义一下就可以;了.
2.1输入代码:
cin>>n; //新加入的会员个数
hy a[n+1]; //定义n+1个会员,因为格斗场初始有一个会员
a[0].id=1; //格斗场初始的会员,编号为1
a[0].s=1000000000; //战力值为100000000
while(n--){ //依次输入
long long x,y; //编号和实力值
cin>>x>>y; //输入
a[i].id=x; //赋值
a[i].s=y; //赋值
find(a,a[i]); //进行查找输出
i++; //下标加1
}
3.查找函数
在上面输入中的代码,我们看到了一个函数find,这就是这个程序的重要点,我们就是需要在a这个会员数组里面,找与a[i]最合适决斗的一个老会员.
我们可以依次枚举查找,利用3个变量来记录,不断的更新和a[i].s绝对值最小的一个老会员,如果有相同的话,我们需要一个特判,那就是找就要找一个软柿子捏,也就是选两个之间实力值更小的那位.
不断的更新之后,枚举所有老会员之后,那3个变量已经是最接近a[i]的了,可以直接输出这3个变量中记录编号ID的那个变量就可以了!
3.1函数代码:
void find(hy a[],hy b){ //找到应该跟哪一个会员进行格斗
long long Min=1000000001,M=0,Id=0; //进行找绝对值最接近的
for(int j=0;j<i;j++){ //依次和前面的老会员枚举查找
long long t=abs(max(a[j].s,b.s)-min(a[j].s,b.s));//求两者的绝对值
if(t==Min){ //如果相等了
if(a[M].s>a[j].s){ //那么就找厉害的打架
M=a[j].s; //实力值赋值
Id=a[j].id; //ID赋值
}
}
else if(t<Min){ //如果小于了
Min=t; //赋值
M=a[j].s; //保存实力值
Id=a[j].id; //保存ID
}
}
cout<<b.id<<" "<<Id<<endl; //输出
}
总代码:
#include<bits/stdc++.h>
using namespace std;
struct hy{ //定义一个会员
long long id; //会员的ID账号
long long s; //会员的实力值
hy(long long _id=0,long long _s=0){//构造函数初始化
id=_id; //赋值
s=_s; //赋值
}
};
int n,i=1; //初始定义
void find(hy a[],hy b){ //找到应该跟哪一个会员进行格斗
long long Min=1000000001,M=0,Id=0; //进行找绝对值最接近的
for(int j=0;j<i;j++){ //依次和前面的老会员枚举查找
long long t=abs(max(a[j].s,b.s)-min(a[j].s,b.s));//求两者的绝对值
if(t==Min){ //如果相等了
if(a[M].s>a[j].s){ //那么就找厉害的打架
M=a[j].s; //实力值赋值
Id=a[j].id; //ID赋值
}
}
else if(t<Min){ //如果小于了
Min=t; //赋值
M=a[j].s; //保存实力值
Id=a[j].id; //保存ID
}
}
cout<<b.id<<" "<<Id<<endl; //输出
}
int main(){
cin>>n; //新加入的会员个数
hy a[n+1]; //定义n+1个会员,因为格斗场初始有一个会员
a[0].id=1; //格斗场初始的会员,编号为1
a[0].s=1000000000; //战力值为100000000
while(n--){ //依次输入
long long x,y; //编号和实力值
cin>>x>>y; //输入
a[i].id=x; //赋值
a[i].s=y; //赋值
find(a,a[i]); //进行查找输出
i++; //下标加1
}
return 0;
}
总结:
这道题算是特别特别难的了,在面对对象的编程中,我没有写类,但是写了一个和类相同之处很多的结构体,运用了不断的更新最接近的绝对值,最后找到合适的对手,算是特别难的,因为在比较的时候,需要3个变量来进行存储,以后继续进行更新.