题解 P5741 【【深基7.例10】旗鼓相当的对手 - 加强版】

SUNCHAOYI · 2020-01-19 14:02:02 · 题解

[upd on 2025.06.23] 老题解清理计划，完善格式后重新提交。

根据题意要输出旗鼓相当的对手：如果某对学生 (i,j) 的每一科成绩的分差都不大于 5，且总分分差不大于 10，那么这对学生就是旗鼓相当的对手。

在这句话中，如果要输出，必须要满足两个条件：每门分差 \le 5；总分分差 \le 10。那么怎么设计呢？是时候运用我们的结构体了：

struct node
{
    string name;//名字 
    int a,b,c,s = 0;//三门科的分数与总分 
} st[1005];

在输入的时候，记得把总分也同步求出来：

st[i].s = st[i].a + st[i].b + st[i].c;//求出每个人的总分 

我们仔细读题，会发现一个输出的限制条件：输出时按照字典序输出所有对手组合。这一个条件就告诉了循环的顺序，又因为所有人的姓名是按照字典序给出的，因此我们只要按顺序进行循环即可。

那么剩下的就简单了，我们只要判断选手是否符合条件，然后进行输出即可：

//选手 i，j 的比较，如果符合条件便直接输出两个选手的姓名 
if(cmp(i,j)) cout<<st[i].name<<" "<<st[j].name<<endl;

cmp() 函数的设计，直接按题意就行了：

bool cmp(int x,int y)//每门科目的条件和总分的条件，用"与&"连接 
{
    if(abs(st[x].a - st[y].a) <= 5 && abs(st[x].b - st[y].b) <= 5 && abs(st[x].c - st[y].c) <= 5 && abs(st[x].s - st[y].s) <= 10) return true;
    else return false;
}

最后思考一个问题：这样进行循环比较会超时吗？

数据范围 N \le 1000。两层循环最多循环次数为 10^6 次，所以能在 1s 中得到结果，因此不会超时啦！

完整代码：

#include <iostream>
#include <cmath>
using namespace std;
struct node
{
    string name;//名字 
    int a,b,c,s = 0;//三门科的分数与总分 
} st[1005];
int n;
bool cmp(int x,int y);
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        cin>>st[i].name>>st[i].a>>st[i].b>>st[i].c;
        st[i].s = st[i].a + st[i].b + st[i].c;//求出每个人的总分 
    }
    for(int i = 1;i <= n;i++)//按顺序进行循环，比较 
    {
        for(int j = i + 1;j <= n;j++)
        {
            //选手i，j的比较，如果符合条件便直接输出两个选手的姓名 
            if(cmp(i,j)) cout<<st[i].name<<" "<<st[j].name<<endl;
        }
    }
    return 0;
} 
bool cmp(int x,int y)//每门科目的条件和总分的条件，用"与&"连接 
{
    if(abs(st[x].a - st[y].a) <= 5 && abs(st[x].b - st[y].b) <= 5 && abs(st[x].c - st[y].c) <= 5 && abs(st[x].s - st[y].s) <= 10) return true;
    else return false;
}