第一次还在提前批里就没参加。🤷‍♀

形式

牛客网评测
5道题，2h。
1道核心代码模式，4道ACM模式。

题

修剪大树

题意

给一棵二叉树，剪掉最少的点变成满二叉树。

分析

开始题写的完全二叉树，跟他提了之后改成满二叉树。
但依然一个点没过，很迷惑。
思路是先计算没有NULL的最大层数，再把这层以下的全删掉。

代码

case通过率0%（只过样例了），不献丑了。

消消乐

题意

给一串数，两个相邻的和为10可以消掉，问最多消多少次。

分析

用栈保存，栈顶与当前和为10就弹出，否则压入。

代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

const int maxn = 1e6 + 5;

int main(int argc, const char * argv[])
{
    int n, a[maxn];
    string str;
    stack<int> s;
    cin >> n >> str;
    for (int i = 0; i < n; i++) {
        a[i] = str[i] - '0';
        if (!s.empty() && a[i] + s.top() == 10) {
            s.pop();
        } else {
            s.push(a[i]);
        }
    }
    cout << s.size() << endl;
    return 0;
}

case通过率：100%

钢索计时

题意

有两个钢索，一群人要过，只有一个平衡木，要两个人一起架着走。
给出每个人过桥的时间，如果一个快的和一个慢和一起过就按慢的时间算。
问最短时间。

分析

不断用时间最少的两个人把平衡木来回带。
比如这样：
要过河：

1 2 3 4 5

1和2先过去

1 2
    3 4 5

1把杆子带回来

  2
1   3 4 5

4和5过去

  2   4 5
1   3

2把杆子带回来

      4 5
1 2 3

1和2再走

1 2   4 5
    3

1带杆子回

  2   4 5
1   3

1和3过

1 2 3 4 5

规律是4次一组：2 1 a[i] 2

代码

找的规律应该还是有疏漏，case通过率90%。
代码改好了再放上来。

共享充电

题意

有n个手机共用一个充电器，给出充电器的充电速度w、每个手机的电量a[i]和耗电速度b[i]，问能保持每个手机都有电的时间最长为多少。

分析

设总充电时间为t，每个手机充电时间为t[i]。

$w*t[i] + a[i] = b[i] * t$

求和得：

$w*t + \sum_{i=0}^n{a_i} = \sum_{i=0}^n{b_i} * t$

所以:

$t = \frac{sum(a[i])}{sum(b[i]) - w}$

但错就错在求完之后代入发现有的t[i]是负数，手机也不能给手机充电啊……

代码

按上面的写case通过率为10%。

砝码

题意

给一些砝码的质量和一个物品的质量，用这些砝码正好称出来k（整数）个物品，求k最小值，不能则输出-1.

分析

来不及了，没做完。

代码

没写。

总结

一个题不会就爬走做下一个，然后下一个不会又换，结果哪个都没做明白。
嚎啕大哭.jpg