题解
NOIP201709宝藏
1 条题解
-
0
#include<bits/stdc++.h> using namespace std; long long x[301000], y[301000], xx[301000], yy[301000], maxx=LONG_LONG_MIN, n, m, k, maxx_x=-1, maxx_y=-1; // x[i]: 第i行的宝藏数量 // y[i]: 第i列的宝藏数量 // xx[i]: 第i个宝藏的行坐标 // yy[i]: 第i个宝藏的列坐标 // maxx: 未使用的变量 // n,m,k: 行数、列数、宝藏数量 // maxx_x: 当前找到的最大行宝藏数 // maxx_y: 当前找到的最大列宝藏数 int main(){ cin >> n >> m >> k; int flagx, flagy; // flagx:最大行对应的行号, flagy:最大列对应的列号 int flag = 0; // 标记(flagx, flagy)位置是否有宝藏,0表示无,1表示有 // 读入所有宝藏位置并统计每行每列的宝藏数 for(int i = 1; i <= k; i++){ cin >> xx[i] >> yy[i]; x[xx[i]]++; // 第xx[i]行宝藏数+1 y[yy[i]]++; // 第yy[i]列宝藏数+1 // 更新最大行和最大列(边读边更新,存在逻辑缺陷) if(maxx_y < y[yy[i]] && maxx_x < x[xx[i]]){ // 当前宝藏所在的行和列都创下新高,同时更新行和列 flagx = xx[i]; maxx_x = max(maxx_x, x[xx[i]]); flagy = yy[i]; maxx_y = max(maxx_y, y[yy[i]]); } else if(maxx_x <= x[xx[i]]){ // 仅当前行创下新高,更新最大行 flagx = xx[i]; maxx_x = max(maxx_x, x[xx[i]]); } else if(maxx_y <= y[yy[i]]){ // 仅当前列创下新高,更新最大列 flagy = yy[i]; maxx_y = max(maxx_y, y[yy[i]]); } } // 检查(flagx, flagy)这个位置是否有宝藏 // 如果有宝藏,激活该位置时会重复计算,需要减1 for(int i = 1; i <= k; i++){ if(xx[i] == flagx && yy[i] == flagy){ flag = 1; // 该位置有宝藏 break; } } // 输出:最大行宝藏数 + 最大列宝藏数 - flag // flag=1表示交点有宝藏需要减1,flag=0表示交点无宝藏直接相加 cout << maxx_x + maxx_y - flag; return 0; }
- 1