hzwer4605 | 肥得更高

Portal

解法很多,机房有巨佬强行用线段树做。

由于每次施肥都会使肥力下降,最小值可以直接贪心解决,不断对肥力最低的施肥即可。如果求最大值,由于施肥使肥力下降,所以不更新当前最优选择显然是错误的。可以考虑用 priority_queue 维护,但由于二叉堆的复杂度为 O(logN)O(\log N) 所以 T 不 T 要看 RP,可以考虑乱搞一波上 pairing_heap,除了 pop()O(logN)O(\log N) 其他操作均为 O(1)O(1),可以轻松水过。
每次只对堆顶进行施肥,故只有堆顶的肥力会下降,如果觉得还不够快,可以考虑用 modify 代替 pop 和 push 规避 O(logN)O(\log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <queue>
#include <cstdio>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag> ph;
const int N=1e6+1;int seq[N];ll f[N];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>=48&&c<=57){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
int main() {
int n=read(),k=read(),cur=k;ll _min=0,_max=0;
for(int i=1;i<=n;++i) seq[i]=read();
for(int i=1;i<=k;++i) f[i]=f[i-1]+i;
std::sort(seq+1,seq+n+1);ph heap;
for(int i=1;i<=n;++i)
if(seq[i]<=cur) _min+=seq[i]*seq[i]-f[seq[i]-1],cur-=seq[i];
else if(cur) {_min+=seq[i]*cur-f[cur-1];break;}
for(int i=n;i>=1;--i) heap.push(seq[i]);
while(k) {
_max+=heap.top();--k;
heap.push(heap.top()-1);heap.pop();
}
printf("%lld %lld",_max,_min);
return 0;
}

Download

吃了 60MiB 的記憶體,有点多。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。