自动搬运

查看原文

来自洛谷，原作者为

	InformationEntropy We must know,and we will know!

搬运于2025-08-24 22:20:50，当前版本为作者最后更新于2020-08-08 21:44:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

给出一个不枚举 1-5 的解法（万一遇到类似的题，但 $a_i,b_i$ 范围大了，那么这种枚举的方法无论是时间上还是空间上都行不通）。

大致思路就是：

• 记录从 1 到第 $2\times n$ 个同学 $a_i$ 的成绩 $s$ 和所属桌号 $pos$ 的值。

• 然后排序，排序规则是成绩小的在前，成绩相同时，桌号小的在前（方便算连续）。

• 排序后从 1 到 $2\times n$ 找，如果找到了一个 $a_i$ 满足 $a_i.s = a_{i+1}.s$ 且 $a_{i+1}.pos-a_{i}.pos =1$，说明他们成绩相同且桌号连续，此时让总和累加1。如遇到一个 $a_i$ 不符合上述标准但 $a_i$ 与 $a_{i+1}$ 是同桌则不打断，否则打断，并更新答案。

• 输出最终答案即可。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline void read(int &x){//快读
    int f = 1;
    x = 0;
    char ch = getchar();
    while(ch<'0' || ch>'9'){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0'&&ch <= '9'){
        x = x*10+ch-48;
        ch = getchar();
    }
    x *= f;
}
struct node
{
    int x, pos;
}a[200001];//定义学生
bool cmp(node a, node b)
{
    if(a.x == b.x) return a.pos < b.pos;
    return a.x < b.x;
    //排序规则，上文已解释
}
int main()
{
    int n;
    read(n);
    for(int i=1; i<=n; i++)
    {
        read(a[i].x);
        a[i].pos = i;
        read(a[i+n].x);
        a[i+n].pos = i;
        //一次读入两个同桌，把桌号都设为i
    }
    sort(a+1, a+2*n+1, cmp);
    int maxl = 0, maxs = 0, s = 1;
    for(int i=1; i<=2*n; i++)
    {
        if(a[i].x==a[i+1].x && a[i+1].pos-a[i].pos==1)
        {
            s++;
            //满足要求则累加答案。
        }else if(a[i].pos!=a[i+1].pos){
            //不满足，打断累加
            if(s>1&&s>maxl)//s>1的作用为如果没加则不更新
            {
                maxl=s;
                maxs=a[i].x;//更新两个的值
            }
            s=1;//重设为一
        }
    }
    cout << maxl << " " << maxs;
    return 0;
}