出题人题解|完美储存

【ZSROI R1-B】完美储存

题目大意：

有若干硬盘，每个硬盘空间为 $S$。有 $n$ 个文件，你需要依次处理他们，对于一个文件 $i$，其需要 $a_i$ 的空间。你一定会把这个文件放进当前剩余容量最大的硬盘内。求最少硬盘数使得空间不会溢出且所有文件均能存储。

$20pts:$

暴力全过程。

#include<bits/stdc++.h>
using namespace std;
int n,s,a[100009];
bool check(int x){
    priority_queue<int> q;
    int sum[100009];
    for(int i = 1;i<=x;++i) sum[i] = s;
    for(int i = 1;i<=n;++i){
        int mx = 0,mxid;
        for(int j = 1;j<=x;++j){
            if(sum[j]>mx){
                mx = sum[j];
                mxid = j;
            }
        }
        if(mx>=a[i]) sum[mxid]-=a[i];
        else return 0;
    }
    return 1;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i = 1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        for(int i = 1;i<=n;++i){
            if(check(i)){
                cout<<i<<'\n';
                break;
            }
        }
    }
}

$40pts:$

见下文满分代码，仅使用一个优化可以得到。

$100pts:$

• 优化一：

因为 $a_i\le S$，所以最坏情况下只需要 $n$ 个硬盘，换句话说就是 $n$ 个硬盘肯定可以，那么即答案具有单调性，于是考虑二分硬盘个数，优化掉一重循环。

• 优化二：

对于每个 $a_i$ 要找剩余最大的硬盘，用优先队列维护当前最大硬盘即可。

#include<bits/stdc++.h>
using namespace std;
int n,s,a[100009];
bool check(int x){
    priority_queue<int> q;
    for(int i = 1;i<=x;++i) q.push(s);
    for(int i = 1;i<=n;++i){
        int j = q.top();
        q.pop();
        if(j>=a[i]) j-=a[i];
        else return 0;
        q.push(j);
    }
    return 1;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i = 1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        int l = 1,r = n;
        while(l<r){
            int mid = (l+r)/2;
            if(check(mid)) r = mid;
            else l = mid+1;
        }
        cout<<l<<endl;
    }
}

时间复杂度：$O(Tnlog^2n)$