（贪心）cf#523-B.Views Matter

http://codeforces.com/contest/1061

给出x，y，呈现俯视图和侧视图，求可以去掉多少块是这两个视图不改变
5 6
3 3 3 3 3
10
首先想到排序，由大到小，在n+1个位置增加一个0的高度块用于解第n个块。
从第2个块开始
对于前一个块高度更高时，已使用块数目 += 高度差
对于当前块比前一块高度相等或者更大时，因为俯视图不能变，所以至少留下一块，即已使用块数目++，将当前块高设为 前一块高-1。特判前一块高度为0时，直接将已使用块数目 += 未处理的数量
相当于用高度设为已处理的y轴，特判为0的情况就行，解法很多。

#include
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int a[maxn];
bool cmp(int x, int y) {return x > y;
}
int main()
{int n, m;while(cin >> n >> m) {ll ans = 0;for(int i = 1; i <= n; i++) {cin >> a[i];ans += a[i];}sort(a + 1, a + n + 1, cmp);a[n + 1] = 0;ll x = 0;for(int i = 2; i <= n + 1; i++) {if(a[i - 1] > a[i])  x += a[i - 1] - a[i];else {if(a[i - 1] == 0) {x += n - i + 2;break;}else x++, a[i] = a[i - 1] - 1;}}cout << ans - x << endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！