㵘[[ARC006C] 積み重ね]

· · 题解

原题

这题太淼了，评橙都没问题……

思路

一眼贪心。

定义一个数组存储每个行李堆堆顶的行李的重量，命名为 t 数组，每次输入 w_i 时遍历一遍 t，如果发现 w_i 小于等于 t 中的某一项，就将这一项设为 w_i，并退出循环，若遍历完没有发现 w_i 小于等于 t 中的某一项（w_i 无法放置在任意一堆上），那么就需要在新建一个堆。

注意：

  2. 换行！

代码

#include <bits/stdc++.h>
using namespace std;
int n , w , t[55] = {0 , (int)1e5 + 5} , ans;
int main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i++)
    {
        cin >> w;
        bool flag = false;
        for (int j = 1 ; j <= ans ; j++)
            if (w <= t[j]) {t[j] = w; flag = true; break;}
        if (!flag) t[++ans] = w;
    }
    cout << ans << endl;
    return 0;
}

评测记录，我竟然错了一次