P1702 突击考试

题目描述

一日,老师决定进行一次突击考试。已知每个学生都有一个考试能力等级,教室里一共有N个课桌,按照顺序排成一列,每张课桌可以坐两个人,第i张课桌坐的两个人的能力等级为(A[i],B[i])。现在老师决定对能力等级为K的人进行测验。他会从这N排中选择连续的L排进行测验,要求这 L排中的每一排至少有一个人考试能力等级为K。现在我们想知道L的最大值以及对应的等级K。

输入格式

第1行:一个整数N;

第2..N+1行:每行两个整数,表示A[i],B[i]。

输出格式

两个整数L和K,要求在L最大的条件下K最小。

输入输出样例

输入 #1
3

3 5

4 5

1 3

输出 #1
2 5

说明/提示

1≤N≤100,000,1≤A[i],B[i]≤5

思路

另f[i][k]表示从第一排到i,k这个等级连续了多少次(截止到k,断开重记),那么对于每排的两个等级x,y,满足:

f[i][x]=f[i-1][x]+1;

f[i][y]=f[i-1][y]+1;

于是我们对于答案maxx和对应的k值max_k,可以用f[i][x]和f[i][y]中较优的一个(更符合题意)来更新答案。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;

int f[N][10];
int n,maxl,maxk;

int main () {
	scanf("%d",&n);
	for(int i=1,x,y; i<=n; i++) {
		scanf("%d%d",&x,&y);
		f[i][x]=f[i-1][x]+1;
		f[i][y]=f[i-1][y]+1;
		int l,k;
		if(f[i][x]>f[i][y]) {
			l=f[i][x];
			k=x;
		}
		if(f[i][x]<f[i][y]) {
			l=f[i][y];
			k=y;
		}
		if(f[i][x]==f[i][y]) {
			l=f[i][x];
			k=min(x,y);
		}
		if(l>maxl) {
			maxl=l;
			maxk=k;
			continue;
		}
		if(l==maxl) {
			maxl=min(maxk,k);
			continue;
		}
	}
	printf("%d %d\n",maxl,maxk);
	return 0;
}

 

上一篇:CF833B The Bakery


下一篇:线性基学习笔记(咕咕咕)