NC15928. Bullet
描述
In GGO, a world dominated by gun and steel, players are fighting for the honor of being the strongest gunmen. Player Shino is a sniper, and her aimed shot kills one monster at a time. Now she is in an n*n map, and there are monsters in some grids. Each monster has an experience. As a master, however, Shino has a strange self-restrain. She would kill at most one monster in a column, and also at most one in a row. Now she wants to know how to get max experience, under the premise of killing as many monsters as possible.
输入描述
The first line contains an integer n.
n<=500
Then n lines follow. In each line there are nintegers, and Aij represents the experience of the monster at grid (i,j).If Aij=0, there is no monster at grid (i,j).The experience is the minimal experience of all the monster which are killed.It guaranteed that the maximum of the experience of the monster is not larger than 109
输出描述
One integer, the value of max experience.
示例1
输入:
2 2 0 1 8
输出:
2
C++14(g++5.4) 解法, 执行用时: 84ms, 内存消耗: 3732K, 提交时间: 2020-10-05 10:50:17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int g[maxn][maxn], c[maxn], r[maxn];
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
c[j] = max(c[j], g[i][j]);
r[i] = max(r[i], g[i][j]);
}
}
int ans = inf;
for (int i = 0 ;i < n; ++i) if (r[i]) ans = min(ans, r[i]);
for (int i = 0 ;i < n; ++i) if (c[i]) ans = min(ans, c[i]);
if (ans == inf) cout << 0 << endl;
else cout << ans << endl;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 125ms, 内存消耗: 2732K, 提交时间: 2022-10-11 22:24:32
#include <bits/stdc++.h>
using namespace std;
long long n,m,ans=0x3f3f3f3f,mp[1005][1005],b[1005],a[1005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>m;
a[i]=max(a[i],m);
b[j]=max(b[j],m);
}
for(int i=1;i<=n;i++)
{
if(a[i])
ans=min(a[i],ans);
if(b[i])
ans=min(b[i],ans);
}
cout<<ans;
}