列表

详情

NC51062. Equivalent Prefixes

描述

Two arrays u and v each with m distinct elements are called equivalent if and only if for all
where denotes the index of the minimum element among .
Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number where and are equivalent.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers .
The third line contains n integers .

* 
* 
*  are distinct.
*  are distinct.
* The sum of n does not exceed .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入: 

2
1 2
2 1
3
2 1 3
3 1 2
5
3 1 5 2 4
5 2 4 3 1

输出: 

1
3
4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 115ms, 内存消耗: 1376K, 提交时间: 2019-08-28 16:06:59 

#include<bits/stdc++.h>
using namespace std;
int n,n1[100011],n2[100011],ans,s1[100010],s2[100010],t1,t2;
int main(){
	while(scanf("%d",&n)!=EOF){
		t1=t2=0;
		for(int i=1;i<=n;i++)scanf("%d",&n1[i]);
		for(int i=1;i<=n;i++)scanf("%d",&n2[i]);
		for(ans=1;ans<=n;ans++){
			while(t1&&s1[t1]>=n1[ans])t1--;
			while(t2&&s2[t2]>=n2[ans])t2--;
			if(t1!=t2)break;
			s1[++t1]=n1[ans],s2[++t2]=n2[ans];
		}
		printf("%d\n",ans-1);
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 131ms, 内存消耗: 1156K, 提交时间: 2020-10-25 20:03:01 

#include<cstdio>
const int maxn=100010;
int a[maxn],b[maxn],l[maxn],r[maxn],n;
int main()
{
	while(~scanf("%d",&n))
	{
		int ans=n,x=0,y=0;
		for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
		for(int i=0;i<n;i++)
		scanf("%d",&b[i]);
		for(int i=0;i<n;i++)
		{
			while(x&&l[x]>a[i])
			x--;
			l[++x]=a[i];
			while(y&&r[y]>b[i])
			y--;
			r[++y]=b[i];
			if(x!=y)
			{
				ans=i;
				break;
			}
		}
		printf("%d\n",ans);
	}
}

上一题

© 2025 nowcoder.com