Problem D: 梯田AGAIN

╰半夏微凉° 2022-06-16 00:16 123阅读 0赞

## Description ##

大家还记得去年的梯田吗？土豪YZK在一块小岛上有着一大片n\*m的梯田，每块1\*1的田地都有它的高度。奴隶们不甘被YZK剥削，他们联合起来决定发动一场海啸淹掉YZK的部分梯田。

奴隶们去年尝试了一下，结果发现，由于土质太过松软，水能够透过土地渗入到相邻的梯田，即对于海啸高度h，梯田中所有小于等于h的土地都会由于土质松软而被被淹没。

现在给你一个n\*m的矩阵，代表梯田中每块田地的高度。然后给定q个询问，每个询问给定一个海啸高度h，问在此高度下，不被淹没的梯田数量是多少。

## Input ##

第一行一个整数T，表示测试数据组数。

对于每组测试数据：

第一行三个数字n，m，q，表示梯田的行数，列数和询问数。

之后n行，每行m个数字，表示每块田地的高度，梯田高度不大于1000000。

之后q行，每行给出一个海啸高度h，问大于这个高度的梯田有多少块。

0<T<20。

0<n，m<=200。

0<=q<1000。

0<=h<=1000000.

## Output ##

对于每个询问，给出一个整数，表示大于这个海啸高度的梯田数量。

## Sample Input ##

22 2 21 23 4232 3 31 2 33 4 5045

## Sample Output ##

21610

思路 :

用一维数组存储,按从大到小排,从数组头开始向后找

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[40010];
    bool cmp(const int &x, const int &y){
    	return x>y;
    }
    int main()
    {
    	int T,i,j,k,n,m,q,h=0,cnt=0;
    	cin>>T;
    	while (T--)
    	{
    		k=0;
    		cin>>n>>m>>q;
    		for (i=0; i<n; i++){
    			for (j=0; j<m; j++){
    			cin>>a[k++];
    			}
    		}
    		sort(a,a+k,cmp);
    		while (q--){
    			cin>>h;
    			cnt=0;
    			for(i=0; i<k; i++){
    				if (a[i] > h){
    					cnt++;
    				}
    				else{
    					break;
    				}
    			}
    			cout<<cnt<<endl;
    		}
    	}
    	return 0;
    }