5-14 电话聊天狂人 (25分)

给定大量手机用户通话记录,找出其中通话次数最多的聊天狂人。

输入格式:

输入首先给出正整数NN(\le 10^5≤10?5??),为通话记录条数。随后NN行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的11位数字构成的手机号码,其中以空格分隔。

输出格式:

在一行中给出聊天狂人的手机号码及其通话次数,其间以空格分隔。如果这样的人不唯一,则输出狂人中最小的号码及其通话次数,并且附加给出并列狂人的人数。

输入样例:

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例:

13588625832 3

搜索树程序:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long LL;
typedef struct Treenode
{
    LL str;
    int cnt;
    struct Treenode* left;
    struct Treenode* right;
}Treenode,*Tree;
Tree Newnode(LL s)
{
    Tree t = (Tree)malloc(sizeof(Treenode));
    t->str = s;
    t->cnt = 1;
    t->left = NULL;
    t->right = NULL;
    return t;
}
Tree Insert(Tree T,LL s)
{
    if(!T)
        T = Newnode(s);
    else if(T->str>s)
        T->left = Insert(T->left,s);
    else if(T->str<s)
        T->right = Insert(T->right,s);
    else
        T->cnt = T->cnt+1;
    return T;
}
void find(Tree T,LL &mins,int &maxt,int &same)
{
    if(T)
    {
        if(T->cnt > maxt)
        {
            maxt = T->cnt;
            mins = T->str;
            same = 1;
        }
        else if((T->cnt==maxt))
        {
            if(T->str<mins)
                mins = T->str;
            same++;
        }
        find(T->left,mins,maxt,same);
        find(T->right,mins,maxt,same);
    }
}
int main()
{
    int n;
    LL t1;
    Tree T;
    cin>>n;
    cin>>t1;
    T =Newnode(t1);
    for(int i=1;i<2*n;i++)
    {
        cin>>t1;
        T = Insert(T,t1);
    }
    LL ms=0;
    int mt=0,num=0;
    find(T,ms,mt,num);
    cout<<ms<<‘ ‘<<mt;
    if(num>1)
        cout<<‘ ‘<<num<<endl;
    else
        cout<<endl;
    return 0;
}

这题一开始用map超时,然后我试了试二叉搜索树,也无情超时,看来必须用hash

时间: 03-25

5-14 电话聊天狂人 (25分)的相关文章

4-9 二叉树的遍历 (25分)

4-9 二叉树的遍历   (25分) 输出样例(对于图中给出的树): Inorder: D B E F A G H C I Preorder: A B D F E C G H I Postorder: D E F B H G I C A Levelorder: A B C D F G I E H 代码:(都是遍历的算法) 1 // 4-9 二叉树的遍历 2 // 3 // Created by Haoyu Guo on 04/02/2017. 4 // Copyright ? 2017 Haoy

5-24 树种统计 (25分)

5-24 树种统计   (25分) 随着卫星成像技术的应用,自然资源研究机构可以识别每一棵树的种类.请编写程序帮助研究人员统计每种树的数量,计算每种树占总数的百分比. 输入格式: 输入首先给出正整数N(\le 10^5≤10?5??),随后N行,每行给出卫星观测到的一棵树的种类名称.种类名称由不超过30个英文字母和空格组成(大小写不区分). 输出格式: 按字典序递增输出各种树的种类名称及其所占总数的百分比,其间以空格分隔,保留小数点后4位. 输入样例: 29 Red Alder Ash Aspe

5-20 表达式转换 (25分)

5-20 表达式转换 (25分) 算术表达式有前缀表示法.中缀表示法和后缀表示法等形式.日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间.请设计程序将中缀表达式转换为后缀表达式. 输入格式: 输入在一行中给出不含空格的中缀表达式,可包含+.-.*.\以及左右括号( ),表达式不超过20个字符. 输出格式: 在一行中输出转换后的后缀表达式,要求不同对象(运算数.运算符号)之间以空格分隔,但结尾不得有多余空格. 输入样例: 2+3*(7-4)+8/4 输出样例: 2 3 7 4

5-3 树的同构 (25分)

5-3 树的同构   (25分) 给定两棵树T1和T2.如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是"同构"的.例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A.B.G的左右孩子互换后,就得到另外一棵树.而图2就不是同构的. 图1 图2 现给定两棵树,请你判断它们是否是同构的. 输入格式: 输入给出2棵二叉树树的信息.对于每棵树,首先在一行中给出一个非负整数NN (\le 10≤10),即该树的结点数(此时假设结点从0到N-1N?1编号):随后NN行,第i

5-17 汉诺塔的非递归实现 (25分)

5-17 汉诺塔的非递归实现   (25分) 借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为"a")通过借助柱(标记为"b")移动到目标柱(标记为"c"),并保证每个移动符合汉诺塔问题的要求. 输入格式: 输入为一个正整数N,即起始柱上的盘数. 输出格式: 每个操作(移动)占一行,按柱1 -> 柱2的格式输出. 输入样例: 3 输出样例: a -> c a -> b c -&g

PTA - - 06-图1 列出连通集 (25分)

06-图1 列出连通集   (25分) 给定一个有NN个顶点和EE条边的无向图,请用DFS和BFS分别列出其所有的连通集.假设顶点从0到N-1N−1编号.进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点. 输入格式: 输入第1行给出2个整数NN(0<N\le 100<N≤10)和EE,分别是图的顶点数和边数.随后EE行,每行给出一条边的两个端点.每行中的数字之间用1空格分隔. 输出格式: 按照"{ v_1v?1?? v_2v?2?? ... v_kv?k?? 

郁闷心情——电话聊天排解法

昨天下午的心情非常的糟糕,就像北京的天气一样,阴霾霭霭,没有蓝天,没有白云,没有微风,甚至连亲爱的太阳都看不到.当然,我的自我调节能力还是有的,我不希望他人的负面情绪影响到我,我不希望自己传递出去的是一些负面的信息,我也更不希望重复犯同样的错误或者总是受他人的掣肘.所以,我提醒自己要不断的学习,不断的提升和完善自我,虽然,我也觉得自己不是一个特别聪明的人,不过每天进步一点点,坚持下去,持续不断的进步,至少能够不断的超越自我也是一件极为开心的事情. 事情是这样的,我现在的工作是比较杂的,有三四个项

PTA 06-图2 Saving James Bond - Easy Version (25分)

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodile

PAT 5-8 File Transfer (25分)

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other? Input Specification: