Problem #2991 - ECNU Online Judge

Li Dao

7 年，8 月前

直接模拟，算每一行最大值，每一列最小值

include

using namespace std;
int T;
int tu[5][5];
int Max[5],Min[5];
void solve()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin>>tu[i][j];
for(int i=0;i<5;i++)
{
Max[i]=tu[i][0];
for(int j=1;j<5;j++) Max[i]=max(Max[i],tu[i][j]);
}
for(int j=0;j<5;j++)
{
Min[j]=tu[0][j];
for(int i=1;i<5;i++) Min[j]=min(Min[j],tu[i][j]);
}

int found=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(tu[i][j]==Max[i] && tu[i][j]==Min[j])
{
found=1;
cout<<i<<’ ‘<<j<<endl;
}
if(!found) cout<<”-1 -1”<>T;
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

回复 1 0

mydream-smc

5 年，4 月前

第二个数据一行有不止3个鞍点，因为我重复了3次没有ac，然后直接5次暴力破解

回复 0 0

Fifnmar

4 年，9 月前

这道题的坑点在于可能有多个最大 / 最小值。但是看样例是可以反应过来的。

#include <cstdint>
#include <cstring>
#include <iostream>
using namespace std;

int main() {
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        uint32_t matrix[5][5];
        for (uint32_t i = 0; i < 5; ++i)
            for (uint32_t j = 0; j < 5; ++j)
                cin >> matrix[i][j];
        bool row_max[5][5];
        bool col_min[5][5];
        memset(row_max, false, sizeof(row_max));
        memset(col_min, false, sizeof(col_min));
        for (uint32_t i = 0; i < 5; ++i) {
            uint32_t crnt_max = matrix[i][0];
            uint32_t crnt_min = matrix[0][i];
            for (uint32_t j = 1; j < 5; ++j) {
                if (crnt_max < matrix[i][j])
                    crnt_max = matrix[i][j];
                if (crnt_min > matrix[j][i])
                    crnt_min = matrix[j][i];
            }
            for (uint32_t j = 0; j < 5; ++j) {
                if (matrix[i][j] == crnt_max)
                    row_max[i][j] = true;
                if (matrix[j][i] == crnt_min)
                    col_min[j][i] = true;
            }
        }
        bool has_saddle_point = false;
        cout << "case #" << query << ":\n";
        for (uint32_t i = 0; i < 5; ++i)
            for (uint32_t j = 0; j < 5; ++j)
                if (row_max[i][j] && col_min[i][j]) {
                    cout << i << ' ' << j << '\n';
                    has_saddle_point = true;
                }
        if (has_saddle_point == false)
            cout << "-1 -1\n";
    }
}

回复 0 0

Fifnmar

3 年，8 月前

一份更好的代码

事实上算最大最小那块可以优化但没必要了。

#include<iostream>

void solve();
using namespace std;

int main() {
    int t;
    cin >> t;

    for (int i = 0; i != t; ++i) {
        cout << "case #" << i << ":\n";
        solve();
    }
}

void solve() {
    // Read matrix.
    int matrix[5][5];
    for (int i = 0; i != 5; ++i) {
        for (int j = 0; j != 5; ++j) {
            cin >> matrix[i][j];
        }
    }

    // Calculate the minimal value of each column.
    int min_of_column[5];
    for (int i = 0; i != 5; ++i) {
        min_of_column[i] = matrix[0][i];
        for (int j = 1; j != 5; ++j) {
            if (min_of_column[i] > matrix[j][i]) {
                min_of_column[i] = matrix[j][i];
            }
        }
    }

    // Calculate the maximal value of each row.
    int max_of_row[5];
    for (int i = 0; i != 5; ++i) {
        max_of_row[i] = matrix[i][0];
        for (int j = 1; j != 5; ++j) {
            if (max_of_row[i] < matrix[i][j]) {
                max_of_row[i] = matrix[i][j];
            }
        }
    }

    // find every saddle point. Note that they are *in order* for we iterate with i in 0..5 and j in 0..5.
    int saddle_points[25][2];
    int cnt = 0; // count of saddle_points.
    for (int i = 0; i != 5; ++i) {
        for (int j = 0; j != 5; ++j) {
            int val = matrix[i][j];
            if (val == max_of_row[i] && val == min_of_column[j]) {
                saddle_points[cnt][0] = i;
                saddle_points[cnt][1] = j;
                cnt += 1;
            }
        }
    }

    // output each.
    if (cnt == 0) {
        cout << "-1 -1\n";
    } else {
        for (int i = 0; i != cnt; ++i) {
            cout << saddle_points[i][0] << ' ' << saddle_points[i][1] << '\n';
        }
    }
}

回复 1 0

CoolCarrot

7 年，8 月前

谁能告诉我测试数据要注意什么？？？
鞍点不止一个超级坑啊，怎么改都是错
如果某一行元素全都相等，那么这个元素到底是不是这行的最大啊？？？
两种试了都是错，sample输出都是对的

回复 0 0

kingno

5 年，8 月前

呃，注意每一行中可能有多个鞍点。第二个数据是这个。

回复 0 0

2991. 鞍点

include

服务

开源

关于我们