安徽省2016“京胜杯”程序设计大赛_D_梯田AGAIN

梯田AGAIN












Time Limit: 5000 MSMemory Limit: 65536 KB
Total Submissions: 95Accepted: 21

Description

大家还记得去年的梯田吗?土豪YZK在一块小岛上有着一大片nm的梯田,每块11的田地都有它的高度。奴隶们不甘被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

2

2 2 2

1 2

3 4

2

3

2 3 3

1 2 3

3 4 5

0

4

5

Sample Output

​2

1

6

1

0

Hint

经测试,此题存在卡输入输出问题,现将时限修改,在此对被卡的同学表示歉意。

另外,由于测评环境为xp,取消对stdio同步对流式输入输出效率可能是不起作用的,请大家务必注意。若怀疑某题存在卡IO的可能,请使用C式io函数或者用io加速外挂进行Io操作。


题解:这题题意写的很清楚,可是要注意一点,要是每次都普通查询操作那么就会超时,此题我是放在了一维数组,然后二分查找实现的,个人觉得此代码写的并不完美,欢迎各位朋友提出宝贵改进意见


#include 
#include
#include

using namespace std;

int a[40010], s;

int search(int start, int end, int key)
{
    int mid, pos = 0;
    while (start < end)
    {
        mid = (start + end) / 2;
        if (a[mid] > key) {
            end = mid;
            pos = end;
        }else {
            start = mid + 1;
            pos = start;
        }
    }
    return pos;
}

int main(int argc, char const argv[])
{
int T, n, m, q, h, i, j;
scanf(“%d”, &T);
while (T–)
{
scanf(“%d%d%d”, &n, &m, &q);
s = n
m;
for (i=0; i<s; i++)
scanf(“%d”, &a[i]);
sort(a, a+s);
while (q–)
{
scanf(“%d”, &h);
if (h < a[0]) printf(“%d\n”, s);
else if (h > a[s-1]) printf(“%d\n”, 0);
else
printf(“%d\n”, s - search(0, s-1, h));
}
}
return 0;
}


坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: Fayne
  • 本文链接: 359.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!