牛客小白月赛 104
传送门：(0条未读通知) 牛客小白月赛104_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
A-小红购买装备（贪心）
只需要写一个结构体或者存tuple，然后按照战斗力降序排序，如果一致按照价格升序排序。遍历一遍数组找到比初始大并且能买下就返回答案即可
代码（c++）：
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>#define ll long longusing namespace std;const int N = 1e5 + 10;struct T{ll u;ll v;ll w;
} a[N];bool cmp(T A, T B){ll x = A.u + A.v, y = B.u + B.v;if(x != y) return x > y;else return A.w < B.w;
}ll n, x, y, z, t;int main()
{cin >> n >> x >> y >> z >> t;for(int i = 1;i <= n;i ++){cin >> a[i].u >> a[i].v >> a[i].w;}sort(a + 1, a + n + 1, cmp);ll ans = x + y, sum = t + z;for(int i = 1;i <= n;i ++){ll mx = a[i].u + a[i].v;if(mx > ans && sum >= a[i].w){ans = mx;sum = sum - a[i].w;break;}}cout << ans << endl;return 0;
}B-小红招募英雄 （二项分布）
这道题是概率论的问题，当然只需要具备高中的概率论知识就行
很明显的二项分布 X~B(n, p)（公式就不写了，忘了可以去百度二项分布计算公式）
n题目已经给了抽10次么， n = 10。p 也給了就是 p4 + p5，求的是P(x >= 2)那不就是：1 - p(x<2)
只需要计算 p(x = 0) 和 p(x = 1)即可
代码（py）：
p1, p2, p3, p4, p5 = map(float,input().split())p = p4 + p5x0 = (1 - p)**10
x1 = (1 - p)**9 * p * 10ans = 1 - (x0 + x1)print(ans)C-小红打怪（二分）
碰到这种问题千万不要暴力去模拟，首先 n 已经是 100000， 在加上 a[i] 是 10 ^ 9,也就是最差要10 ^ 9轮，暴力肯定超时别去浪费时间
那肯定是要去优化，尽可能一次找到轮数，用二分。
这里虽然不满足单调性，但是还是可以用二分，因为只需要判断怪物是否全部死了即可。如果当前轮数没有全部打死就往跳到[mid + 1, r], 全部打死了就跳到 [l, mid]
这样的话复杂度就 log2 的 10^9 * 10 ^ 5 大概就是 3 * 10^6 那就没问题了
代码（c++）：
#include <iostream>#define ll long longusing namespace std;const int N = 1e5 + 10;
int a[N], b[N];int n;bool check(int mid){ll f1 = mid, f2 = mid;for(int i = 1;i <= n;i ++) b[i] = max(a[i] - mid, 0);for(int i = 1;i < n;i ++){if(!f1) break;if(b[i] > 0 && b[i + 1] > 0){int x = min(b[i], b[i + 1]);if(f1 >= x){f1 -= x;b[i] -= x, b[i + 1] -= x;}}}ll sum = 0;for(int i = 1;i <= n;i ++) sum += b[i];return f1 + f2 >= sum;
}int main()
{cin >> n;for(int i = 1;i <= n;i ++) cin >> a[i];int l = 1, r = 1e9;while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << l << endl;return 0;
}
