梯田AGAIN
| Time Limit: 5000 MS | Memory Limit: 65536 KB |
| Total Submissions: 95 | Accepted: 21 |
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
2
2 2 2
1 2
3 4
2
3
2 3 3
1 2 3
3 4 5
0
4
5
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
1
6
1
0
Hint
经测试，此题存在卡输入输出问题，现将时限修改，在此对被卡的同学表示歉意。
另外，由于测评环境为xp，取消对stdio同步对流式输入输出效率可能是不起作用的，请大家务必注意。若怀疑某题存在卡IO的可能，请使用C式io函数或者用io加速外挂进行Io操作。
另外，由于测评环境为xp，取消对stdio同步对流式输入输出效率可能是不起作用的，请大家务必注意。若怀疑某题存在卡IO的可能，请使用C式io函数或者用io加速外挂进行Io操作。
题解：这题题意写的很清楚，可是要注意一点，要是每次都普通查询操作那么就会超时，此题我是放在了一维数组，然后二分查找实现的，个人觉得此代码写的并不完美，欢迎各位朋友提出宝贵改进意见
#include <iostream>
#include <algorithm>
#include <cstdio> 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;
}