Gym101620H – Hidden Hierarchy

传送门:这里

模拟的水题,网上的题解都在说什么奇怪的数据结构,也有字典树写法。然而……

我是直接用map过的……

#include<bits/stdc++.h>
using namespace std;
int n;

struct node{
	long long val=0;
	long long son=0;
	long long must_display=false;
	long long must_expand=false;
};

bool collapse=false;
long long collapse_size=0;
string collapse_element;
map<string, node > file_tree;
string s[1002];
vector<string> temp;
long long val[1002];
long long th_limit;
        
int main()
{
	ios::sync_with_stdio(false);
    cin >> n;
    for(int j=1;j<=n;j++)
    {
    	cin >> s[j] >> val[j];
    }
    cin >> th_limit;
    for(int j=1;j<=n;j++)
    {
    	temp.clear();
        for(int i=0;s[j][i];i++)
        {
            if(s[j][i]=='/')
            {
                temp.push_back(s[j].substr(0,i+1));
                file_tree[temp.back()].val+=val[j];
                file_tree[temp.back()].son++;
                if(file_tree[temp.back()].val>=th_limit)
                {
                	file_tree[temp.back()].must_display=true;
	                for(int k=0;k<temp.size()-1;k++)
	                {
	                	file_tree[temp[k]].must_expand=true;
					}
				}
            }
        }
        file_tree[temp.back()].son--;
	}
    for(auto const & x: file_tree)
    {
    	if(collapse && x.first.substr(0,collapse_size)==collapse_element) ;
		else
		{
			if(x.second.son==0) cout << "  ";
	    	else if(x.second.must_expand) cout << "- ";
	    	else 
	    	{
	    		cout << "+ ";
				collapse=true;
				collapse_size=x.first.size();
				collapse_element=x.first;
			}
			cout << x.first  << " " << x.second.val << endl;
		}
	}
	return 0;
}

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注