简单问题
时间限制:1000 ms | 内存限制:65535 KB难度:2
- 描述
- 给你一个n*m的矩阵,其中的元素每一行从左到右按递增顺序排序,每一列从上到下按递增顺序排序,然后给你一些数x,问这些书在不在这个矩阵中,若在,输出其列号最大的元素坐标。
- 输入
- 多组测试样例,首先两个数n,m(0<n,m<=1000)
然后n行m列的一个矩阵,其中的元素保证在32位整型范围
然后一个数cnt,表示询问数的个数(0<cnt<=100)
然后是cnt个要询问的元素 - 输出
- 如果存在,输出其列号最大的元素坐标
否则,输出“NO” - 样例输入
-
4 4
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
3
7 8 14 - 样例输出
-
3 2
1 3
NO解题思路:虽然用二分可以处理,但是用O(n+m)的复杂度过。由于矩阵是有特殊关系的。从每行左向右递增,每列从上向下递增。于是从第一行最右端起,如果元素大于要找的值,则往左移动,因为该列下边的值都比该元素,如果该元素小于要找的值,则向下移动,继续按照上边的方法判断,如果要找的位置不在矩阵内了,说明没有元素在矩阵中,否则输出位置即可。#include<bits/stdc++.h>
using namespace std;
int a[2000][2000];
int main(){
int n,m,q,aim,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
}
scanf("%d",&q);
for(int j=0;j<q;j++){
scanf("%d",&aim);
int y=m-1,x=0;
bool flag=0;
while(true){
if(a[x][y]>aim){
y--;
if(y<0){
flag=1;
break;
}
}else if(a[x][y]<aim){
x++;
if(x>=n){
flag=1;
break;
}
}else{ break;}
}
if(flag){
printf("NO\n");
}else{
printf("%d %d\n",x+1,y+1);
}
}
}
return 0;
}