K确定的位置【noip模拟赛3】

发表于 | 分类于 ， | 阅读量 次

描述

hzy很喜欢了解歌曲的排行榜，他每次都从XX网站获知。

由于这个网站想对这个歌曲的排行榜含蓄的告诉大家，组织了一个“猜榜大赛”。

这个网站宣布一些歌曲的信息，那些歌曲在歌曲榜上的前几名

例如：

·”qianlizhiwai” 是在榜上的前三名

·”qianlizhiwai”,”dachengxiaoai” 是在歌曲榜的前两名

网站不会把歌曲的名次十分明确的告诉你，他就是想让你通过这些信息，推出一部分歌曲的名次，现在困惑的hzy找您帮忙，想让您推出所有确定名次的歌曲。

输入

第一行包括一个整数n, 1≤n≤500，表示网站给你的信息的条数。

下面n行包括一条信息，形式为”A and B song1 song2 song3 … songA”,1≤A≤B≤100，表示”song1”,”song2”,…,”songA”是在歌曲榜的前B位。

每一首歌都是一个string,由最多25个小写字母组成。

输出

输出可以知道的所有的歌的排名，形式:”Position Song”位置必须有序。

输入样例 1

2 1 and 3 lonely
2 and 2 trebami jasekonja

输出样例 1

3 lonely

输入样例 2

3 2 and 2 pjesma1 pjesma2
3 and 4 pjesma1 pjesma3 pjesma4
1 and 3 pjesma4

输出样例 2

3 pjesma4
4 pjesma3

来源：
来自 <http://www.dingbacode.com/contest/19/problem/K>

题解：
记录最低排名，如果排名i的人位置确定，那么前i-1的人数为i-1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

struct Coke{
int lnumber;
string name;
}singer[1000000];
int tot=0;
map<string,int >mp;
map<string,int >Yw;
int ranking[1000000];

vector<int >ans;

bool cmp(Coke a,Coke b)
{
    return a.lnumber<b.lnumber;
}


int main()
{

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int A,B;
        char s[20];
        cin>>A>>s>>B;
        for(int j=1;j<=A;j++)
        {
            string ming;
            cin>>ming;
            if(mp[ming])
            {
                int k=Yw[ming];
                singer[k].lnumber=min(B,singer[k].lnumber);
            }
            else
            {
                mp[ming]=B;
                singer[++tot].name=ming;
                singer[tot].lnumber=B;
                Yw[ming]=tot;
            }
        }
    }

    int mr=0;
    for(int i=1;i<=tot;i++)
    {
        int k=singer[i].lnumber;
        ranking[k]++;
        mr=max(mr,k);
    }

    for(int i=1;i<=mr;i++)
        ranking[i]+=ranking[i-1];


    sort(singer+1,singer+1+tot,cmp);
    for(int i=1;i<=tot;i++)
    {
        if(ranking[singer[i].lnumber-1]==singer[i].lnumber-1)
            ans.push_back(i);
    }

    for(vector<int>::iterator it=ans.begin();it!=ans.end();it++)
    {
        cout<<singer[*it].lnumber<<" "<<singer[*it].name<<endl;
    }

    return 0;
}