疯狂动物城报名

常规
1

3. 疯狂动物城报名

XJOI - 题目ID：8378选做题100分

最新提交：

Time Limit Exceeded

50 分

历史最高：

Time Limit Exceeded

50 分

时间限制: 1000ms

空间限制: 65536kB

题目描述

题目描述

在听说兔子成了最好的警官后，疯狂动物城的其他动物都跃跃欲试来警局报名，也想成为一个除暴安良的伟大警官。来报名的有蜜獾、蜗牛、蚂蚁、长颈鹿……对于群众们的热情，警长很是无奈。为了维持秩序，牛局长让所有来报名的动物按照身高从低往高排队（身高全部取整数）。现在他想知道几个身高数据正好是某值的动物，在队伍中的起止位置，于是他把任务交给了猎豹警官。由于人数太多，一个个数实在太慢了，现在请你帮猎豹警官编程求解（如果队伍中没有此身高的，那么位置记为-1）。

比如队伍中有 6 个动物，他们的身高为：1 3 3 3 8 8，牛局长让猎豹警官统计了 4 个身高值，分别是 3 1 8 9，那么：

身高为 3 的动物首次和最后一次出现的位置分别是：2 4；

身高为 1 的动物首次和最后一次出现的位置分别是：1 1；

身高为 8 的动物首次和最后一次出现的位置分别是：5 6；

身高为 9 的动物首次和最后一次出现的位置分别是：-1 -1；

输入格式

第一行两个整数 n、m，分别表示队伍人数、局长要统计的身高数目；

第二行 n 个整数，代表报名队伍中各动物的身高，从小到大；

第三行是 m 个整数，代表每一个要统计的身高值 x。

输出格式

总共 m 行，每行两个整数，表示身高一致的动物所在队伍的起止位置

输入样例

10 4 1 3 7 11 11 13 13 13 19 23 3 7 11 13

输出样例

2 2 3 3 4 5 6 8

数据范围

1≤n≤1000001≤n≤100000; 1≤m≤1000001≤m≤100000; 1≤x≤1000001≤x≤100000;

样例解释

身高为 3 的动物首次和最后一次出现的位置分别是：2 4； 身高为 1 的动物首次和最后一次出现的位置分别是：1 1； 身高为 8 的动物首次和最后一次出现的位置分别是：5 6； 身高为 9 的动物首次和最后一次出现的位置分别是：-1 -1；
谁能告诉我该怎么改成100分

#include<bits/stdc++.h>
using namespace std;
int a[100000005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		int l=1,r=n,s=-1,h=-1;
		while(l<=r){
		 	l++;
		 	r--;
		 	if(a[l]==x&&s==-1){
		 		s=l;
			}
			if(a[r]==x&&h==-1){
		 		h=r;
			}
		}
		cout<<s<<" "<<h<<endl;
	}
	return 0;
}
1 个赞
2

我问一下：你这l++，r–干啥用的？
（如果是二分的话，你这代码错了60%）

1 个赞
3

二分不是找中间值吗？你怎么l++，r–了？
二分模版：

#include<bits/stdc++.h>
using namespace std;
int main(){
    while(l+1<r){
		int mid=(l+r)/2;
		if(....){
			l=mid or r=mid;
		}else{
			r=mid or l=mid;
		}
	}
	cout<<..;
}
1 个赞
4

改成：

        while(l<=r){
		 	int mid=(l+r)/2;
		 	if(a[l]<=x){
		 		l=mid;
			}
			else{
                r=mid;
            }
		}
1 个赞
5 
#include<bits/stdc++.h>
using namespace std;
int a[100000005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		int l=1,r=n,s=-1,h=-1;
		while(l<=r){
		 	int mid=(l+r)/2;
		 	if(a[l]<=x){
		 		l=mid;
			}
			else{
                r=mid;
            }
		}
		cout<<s<<" "<<h<<endl;
	}
	return 0;
}

TLE0分

1 个赞
6

66

1 个赞
7

你好像没明白为什么用二分

1 个赞
8 
#include<bits/stdc++.h>
using namespace std;
int a[100000005];
map<int,int> q;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		q[a[i]]++;
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
        if(q[x]==0){
			cout<<-1<<" "<<-1<<endl;
			continue;
		}
		int l=1,r=n;
		while(l+1<r){
		 	int mid=(l+r)/2;
		 	if(a[mid]<x){
		 		l=mid;
			}
			else{
                r=mid;
            }
		}
		cout<<l+1<<" ";
		l=1,r=n;
		while(l+1<r){
			int mid=(l+r)/2;
			if(a[mid]<=x){
				l=mid;
			}
			else{
		        r=mid;
		    }
		}
		cout<<l<<endl;
	}
}

给你看看我WA50的代码看看二分的思路

1 个赞