Opening Ceremony（贪心）

Problem E: Opening Ceremony

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 137  Solved: 30
[Submit][Status][Web Board]

Description

Input

Output

Sample Input

6
2 1 8 8 2 3

Sample Output

5

HINT

题意：有一堆砖块，每一次操作可以选择消去任意一行，也可以选择消去任意一列。求要消去所有的砖块需要最小的操作数。

思路：贪心。每次进行消一行操作时，显然消最底层的一行比消高层更优（这样可以消掉更多的砖块）。每次进行消一列操作时，显然消最高的一列比消更矮的一列更优。

那么只要从小到大排序，然后遍历一次就可以了。

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        int mmin=n;
        for(int i=1;i<=n;i++)
        {
            mmin=min(mmin,(n-i+a[i]));//i+1之后消列，i前除行。
        }
        printf("%d
",mmin);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1578
    User: aking2015
    Language: C++
    Result: Accepted
    Time:56 ms
    Memory:1356 kb
****************************************************************/

其实，消列和消行顺序对最终结果没有影响的（只对中间过程有影响）。