1 条题解

  • 0
    @ 2025-4-7 15:47:22

    🧠 题解(Solution)

    本题是一个计数统计 + 排序输出问题,主要考察以下算法思路:

    ✅ 解题思路

    使用哈希表统计每个树种的出现次数:

    map<string, int> species_count;
    

    使用字符串作为 key 来存储树种,遇到重复树种进行加一计数;

    统计总树木数 TT,每读取一行即 T++T++

    最后按字母顺序输出:

    使用 map(自动按字母排序);

    每个树种占比 = 出现次数 / 总数 * 100;

    输出保留 44 位小数,使用 printf("%.4f") 或 setprecision(4)。

    🧮 百分比计算公式

    设:

    总树数为 TT

    某个树种的数量为 cc

    则该树种所占百分比为:

    𝑐 𝑇 × 100 T c ​ ×100

    输出时保留 44 位小数。

    ⏱ 时间复杂度分析

    读取 NN 行输入:O(N)O(N)

    哈希表统计:O(1)O(1) 平均;

    排序输出:O(MlogM)O(M \log M)MM 是不同树种数量;

    总体效率极高,适合处理百万级数据(建议使用 scanf() 加速输入)。

    代码实现

    #include<iostream> 
    #include<cstdio>
    #include<string>
    #include<algorithm>
    
    using namespace std;
    
    int sum=0;
    
    typedef struct node{
    	string word;
    	struct node *l,*r;
    	int cnt,height;
    }*AVLTree;
    
    AVLTree rt;
    string w;
    
    inline int Height(AVLTree T)//计算高度,防止为空时无值 
    {
    	if(T==NULL) return 0;
    	return T->height;
    }
    
    void updateHeight(AVLTree &T)
    {
    	T->height=max(Height(T->l),Height(T->r))+1;
    }
    
    AVLTree LL_Rotation(AVLTree &T)//LL旋转
    {
    	AVLTree temp=T->l;
    	T->l=temp->r;
    	temp->r=T;
    	updateHeight(T);//更新高度
    	updateHeight(temp);
    	return temp;
    }
    
    AVLTree RR_Rotation(AVLTree &T)//RR旋转
    {
    	AVLTree temp=T->r;
    	T->r=temp->l;
    	temp->l=T;
    	updateHeight(T);//更新高度
    	updateHeight(temp);
    	return temp;
    }
    
    AVLTree LR_Rotation(AVLTree &T)//LR旋转
    {
    	T->l=RR_Rotation(T->l);
    	return LL_Rotation(T);
    }
    
    AVLTree RL_Rotation(AVLTree &T)//RL旋转
    {
    	T->r=LL_Rotation(T->r);
    	return RR_Rotation(T);
    }
    
    AVLTree Insert(AVLTree &root,string s)
    {
    	if(root==NULL)
    	{
    		AVLTree p=new node;
    		p->l=p->r=NULL;
    		p->cnt=1;
    		p->word=s;
    		root=p;
    	}
    	else if(s==root->word)
    		root->cnt++;
    	else if(s<root->word)
    	{
    		root->l=Insert(root->l,s);//注意插入后返回结果挂接到root->l
    		if(Height(root->l)-Height(root->r)==2)//插入后看是否平衡,如果不平衡显然是插入的那一边高度大
    		{                                         //沿着高度大的那条路径判断
    			if(s<root->l->word)//判断是LL还是LR,即插入的是lchild节点的lchild 还是rchild
    				root=LL_Rotation(root);
    			else
    				root=LR_Rotation(root);
    		}
    	}
    	else
    	{
    		root->r=Insert(root->r,s);//注意插入后返回结果挂接到root->l
    		if(Height(root->r)-Height(root->l)==2)//插入后看是否平衡,如果不平衡显然是插入的那一边高度大
    		{                                         //沿着高度大的那条路径判断
    			if(s>root->r->word)//判断是LL还是LR,即插入的是lchild节点的lchild 还是rchild
    				root=RR_Rotation(root);
    			else
    				root=RL_Rotation(root);
    		}
    	}
    	
    	updateHeight(root);
    	return root;
    }
    
    void midprint(AVLTree root)
    {
    	if(root!=NULL)
    	{
    		midprint(root->l);
    		cout<<root->word;
    		printf(" %.4lf\n",((double)root->cnt/(double)sum)*100);
    		midprint(root->r);
    	}
    }
    
    int main()
    {
    	rt=NULL;//初始化 
    	while(getline(cin,w))//输入完回车
    	{
    		Insert(rt,w); 
    		sum++;
    	}
    	
    	midprint(rt);
    	return 0;
    }
    
    
    
    • 1

    信息

    ID
    1419
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者