列表

详情

NC223708. FarmingMars

描述

It has been ten years since the miserable day that you won a one-way ticket to Mars on a game show. Your colony’s attempt at terraforming Mars has faced nothing but hardship during that time. The latest disaster: a complete failure of the potato crop. You will have to start planting potatoes again from scratch. Your colony has prepared an n-acre strip of arable land on which you will attempt to plant new potatoes.

 Your scientists have developed bioengineered potatoes that can withstand the harsh Martian climate and almost complete lack of atmosphere. Unfortunately, these potatoes have extreme sensitivity to pH: they will only thrive if the pH of the soil is exactly right, down to six decimal digits. Your bioengineers can create new potato varieties with any specific allowable pH value, but doing so is only economical if you can then plant a large patch of the variety on a continuous interval [l, r] of the n-acre strip. Given a list of pH values measured on each acre of the strip, and a list of potential subintervals [l, r] where you are considering planting potatoes, compute whether a strict majority of the acres within the interval all share the exact same pH value (otherwise it is not worth trying to plant potatoes there). Note that these acres with equal pH value do not need to be contiguous, so long as they all lie within the interval [l, r].

输入描述

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 10 000), the size of the strip ofland and the number of queries, respectively. The next n lines contain a single real number: the ith such number isthe pH of the ith acre along the strip. Each pH value lies between 0.000000 and 14.000000, inclusive, and containsexactly six decimal digits after the decimal point. Then follows m lines containing two space-separated integers each:the bounds lj and rj of the  query (1 ≤ lj ≤ rj ≤ n).

输出描述

Print m lines of output, one for each query. On line j, print  if a strict majority of the land between acres lj and rj (inclusive) all share the exact same pH value, and  otherwise

示例1

输入: 

8 4
7.000000
8.314634
7.000001
7.000000
2.581236
7.000000
2.581236
7.000000
1 8
1 3
4 8
5 7

输出: 

unusable
unusable
usable
usable

原站题解

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

C++ 解法, 执行用时: 182ms, 内存消耗: 600K, 提交时间: 2021-08-19 18:07:27 

#include<bits/stdc++.h>
using namespace std;

int a[10004];

int main(){
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		double d; cin>>d;
		a[i]=d*1000000;
	}
	while(m--){
		int l, r; cin>>l>>r;
		int v=0,c=0;
		for(int i=l;i<=r;i++){
			if(c==0)v=a[i],c=1;
			else{
				if(v==a[i])++c;
				else --c;
			}
		}
		c=0;
		for(int i=l;i<=r;i++)if(a[i]==v)++c;
		if(c>=(r-l+1)/2+1)puts("usable");
		else puts("unusable");
	}
    
    return 0;
}

上一题

© 2025 nowcoder.com