E - Opening Ceremony（贪心）

For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demolished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explosions, one for each tower block, but time constraints now require a hastier solution.

To help you remove the blocks more rapidly you have been given the use of a Universal Kinetic / Incandescent Energy Particle Cannon (UKIEPC). On a single charge, this cutting-edge contraption can remove either all of the floors in a single tower block, or all the x-th floors in all the blocks simultaneously, for user’s choice of the floor number x. In the latter case, the blocks that are less than x floors high are left untouched, while for blocks having more than x floors, all the floors above the removed x-th one fall down by one level.

Task

Given the number of floors of all towers, output the minimum number of charges needed to eliminate all floors of all blocks.

Input

The first line of input contains the number of blocks n, where 2≤n≤100000. The second line contains n consecutive block heights hi for i=1,2,…,n, where 1≤hi≤1000000.

Output

Output one line containing one integer: the minimum number of charges needed to tear down all the blocks.

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

输入：第一行有一个正整数N(1<=N<=100000)表示有N列砖块。第二行有N个正整数（都不超过1000000），表示每一列砖块的数量。

输出：最少操作次数。

解析：

贪心。每次进行消一行操作时，显然消最底层的一行比消高层更优（这样可以消掉更多的砖块）。每次进行消一列操作时，显然消最高的一列比消更矮的一列更优。所以每一次当我说消一行时一定是指消最底层，当我说消一列时一定是指消最高的一列。

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

a.先进行2次消行操作，再进行1次消列操作。

b.先进行1次消列操作，再进行2次消行操作。

c.先进行1次消行操作，再进行1次消列操作，又进行1次消行操作。

这三种操作得到的结果都是一样的

所以最终得到的图形都是一样的，只与消行操作和消列操作的次数有关，而与操作顺序无关。

每次枚举消列操作的次数为m次（0<=m<=N） 那么消完所有砖块的操作次数是 m + 第m+1大High[i]

换句话说就是先把High排成降序，枚举m。先把m以左的消列，再把m+1以右的消行。消完所有砖块的操作次数就是m + High[m+1]，找一个最小值输出即可。

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int s[100100];
    memset(s,0,sizeof(s));
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)
        cin>>s[i];
    sort(s+1,s+n+1,cmp);
    int sum = n;
    for(int i = 0;i<n;i++)
        sum = min(sum,i+s[i+1]);
    cout<<sum<<endl;
    return 0;
}