自动搬运

查看原文

来自洛谷，原作者为

	loceaner forever young

搬运于2025-08-24 22:03:12，当前版本为作者最后更新于2019-05-06 08:27:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

挺长时间不见，这个题竟然变成普及/提高-了？

[题意]

这个题大概意思是linux目录，n条记录，每条记录代表一个目录下有个大小为val文件

然后根目录为“/”；

现在给个t问对于这个目录下的所有文件大小

如果大于t那么“-”展开，

如果小于t那么“+"折叠

如果是底层目录了，那么输出""一个空格，

后面都要跟着目录信息，和目录的大小；

如果是”-“，则进入到子目录中循环操作，目录按字典序输出

[思路]

就是模拟了，节点存储用map容器里面价格set

考虑到超时问题，一律用scanf不用cincout，string转化char输出

string调用”.c_str“函数

把串截开，用charss[i+1]赋值0s就是i+1前面的内容；

目录就是一颗数，dfs遍历下去把文件大小计算出来

然后第二次dfs输出

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+7;

map<string,set<string> >mp;
map<string,ll> mp_size;
ll t;
void dfs1(string str) {
	for(auto next_str:mp[str]) {
		dfs1(next_str);
		mp_size[str]+=mp_size[next_str];
	}
}
void dfs2(string str) {
	if(mp[str].size()==0) {
		printf("  %s %lld\n",str.c_str(),mp_size[str]);// 空
		return ;
	}
	bool flag=true;
	for( auto next_str: mp[str]) // 循环遍历当前目录下的所有目录 看是不是存在子目录 >t
		if(mp_size[next_str]>=t)
			flag=false;
	if(flag) { // 没有 直接输出 +
		printf("+ %s %lld\n",str.c_str(),mp_size[str]);
	} else { // 又有的话 下一层
		printf("- %s %lld\n",str.c_str(),mp_size[str]);
		for(auto next_str:mp[str])
			dfs2(next_str);
	}
}
int main() {
	int n;
	scanf("%d",&n);
	mp_size.clear();
	for(int i=1; i<=n; i++) {
		char s[MAXN];
		ll val;
		scanf("%s%lld",s,&val);
		string fa="//";
		for(int i=0; s[i]; i++) {
			if(s[i]=='/') {
				char temp=s[i+1];
				s[i+1]=0;
				mp[fa].insert(s);
				fa=s;
				s[i+1]=temp;
			}
		}
		mp_size[fa]+=val;
	}
	scanf("%lld",&t);
	dfs1("//");
	dfs2( *(mp["//"].begin()) );
	return 0;
}