pdd实习笔试

4道算法题1h20min才做完QAQ，忘了求中位数的堆做法了，然后推了好久。。。

T1，给字符串11a88b2c这种形式，输出11个a，88个b，2个c

模拟

T2，

数1的个数,法A尽量给两个生命值为1的

ans=(cnt+1)/2+(n-cnt1)

T3,n个人，每个人给个只有ABC的string，给定ABC的数量上限和单价，求满足每个人意愿的最小花费，不满足的话求最多满足多少人的意愿

最hard的一道，我用了两个dp

第一问，f[i][j][k]表示前i人用j个A、k个B、t个C的最小花费。其中t = i - j - k,可以优化掉的一维

第二问，不满足的话，忽略掉单价的信息，做一遍新的dp，g[i][j][k][t]表示前i个人一共用了j/k/t个A/B/C的最多满意人数，然后滚动数组优化掉第一维

T4，给一个数组，求n个中位数和平均数

开始不会堆做法，一开始打了用树状数组每次暴力求中位数的做法O(nlogn方)，tle了，感觉不会tle啊，还给3s，不懂

最后写了两个堆做法过的O(nlogn)