题解：P13499 「Cfz Round 6」Umiyuri Kaiteitan

思路

注意到文件大小取决于执行该命令时系统中已存在的文件数量和它们的文件名长度。

所以我们可以只用记录以下内容：

哪些文件已经被创建
当前总字符数（包括文件名和空格）
当前文件数量

接着遍历每个操作，如果是新文件，更新文件数量和总字符数，记录当前总字符数到对应文件的答案中。

时间复杂度为

O(n + m)

。

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int n,m;
int ops[MAXN];
long long ans[MAXN];
bool created[MAXN];

int digit_len(int x){
    int len=0;
    while(x){
        len++;
        x/=10;
    }
    return len;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>ops[i];
    }
    
    long long total=0;
    int count=0;
    
    for(int i=0;i<n;i++){
        int file=ops[i];
        if(!created[file]){
            created[file]=true;
            count++;
            if(count>1) total++;
            total+=digit_len(file);
        }
        ans[file]=total;
    }
    
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<" ";
    }
    
    return 0;
}

题解：P13499 「Cfz Round 6」Umiyuri Kaiteitan

文章操作

思路

AC 代码

相关推荐

评论

题解：P13499 「Cfz Round 6」Umiyuri Kaiteitan