2021牛客多校#5 (待补充) - sunnyday0725 - D1h.Net第一号博客
返回主页

sunnyday0725

2021牛客多校#5 (待补充)

2021牛客多校#5

B Boxes

这一题是求期望,对于hint的使用,我们发现我们要么一次不用,要么最多用一次,因为你用一次之后,你每次打开一个盒子,都会知道剩下盒子的情况,所以我们分别计算这两种方案然后取min即可。

1.不用hint:ans = Σw[i]

2.用hint:ans = c + Σsum[i] * (1/2)^(n-i) 其中sum[i]表示开前i个盒子(根据花费升序排列)所需的费用,(1/2)^(n-i)表示后面n-i个盒子里面颜色一致,那么就不用开了。

最后两种ans取一个min即可。

code
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n; double sum[N], w[N]; double res, ans, c; int main() { scanf("%d%lf", &n, &c); for (int i = 1; i <= n; i ++ ) { scanf("%lf", &w[i]); res += w[i]; } sort(w + 1, w + n + 1); for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + w[i]; ans += c; for (int i = 1; i <= n - 1; i ++ ) ans += sum[i] * pow(0.5, n - i); ans = min(ans, res); printf("%.6f\n", ans); return 0; } 
K King of Range (单调队列)

朴素一点的思路,我们可以枚举右端点r,然后搜索[1, r - 1]寻找满足条件的最靠右的l,但是会t。

所以要优化,我们维护两个单调队列,一个是单调上升,一个是单调下降的队列,我们发现队列中不仅存的值是单调的,他们对应的下标也是单调的。以维护qm为例(单调下降队列),每次遍历到一个a[r],那么要拿a[r]与其队尾作比较,如果a[r] >= a[qm.back()] 说明此时队列这个值不仅小于a[r],而且相比于a[r]距离r更远,一定是劣于a[r]的。这样维护两个队列之后,我们不断的访问两个队列的对头,不断的将满足条件的两个队首里面下标较小的弹出,一步一步直到找到满足条件的下标最大的一个l,因为此时l满足条件,所以[1, l - 1]为左端点时也一定满足条件,那么此时以r为右端点的情况下的贡献就是l。

code
#include <bits/stdc++.h> using namespace std; const int N = 100010; long long n, m; long long a[N]; void solve() { int k; long long ans = 0; cin >> k; int l = 0;//要找的最靠右的l deque<int> qm, qn;//双端队列,方便维护 for (int r = 1; r <= n; r ++ ) { //维护两个队列 while (qm.size() && a[r] >= a[qm.back()]) qm.pop_back(); qm.push_back(r); while (qn.size() && a[r] <= a[qn.back()]) qn.pop_back(); qn.push_back(r); //不断的访问队头元素,不断更新更优的l while (qm.size() && qn.size() && a[qm.front()] - a[qn.front()] > k) { if (qm.front() > qn.front()) l = qn.front(), qn.pop_front(); else l = qm.front(), qm.pop_front(); } //记录贡献 ans += 1ll * l; } cout << ans << endl; } int main() { ios::sync_with_stdio(0);cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> a[i]; while (m -- ) solve(); return 0; } 
posted @ 2021-08-02 00:08  sunnyday0725  阅读(17)  评论(0编辑  收藏  举报
Copyright © 2021 sunnyday0725
Powered by .NET 6 on Kubernetes

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备