题解 P6444 【[COCI2010-2011#1] PROFESOR 】

InformationEntropy · 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;
}