喵喵的Logo

时间: 1ms        内存:128M

描述:

喵喵是一家科技公司的实习程序员。这一天,他的公司正在换新Logo。为了设计他们公司的Logo,公司的卓BOSS花重金请了许多专业设计师设计了许多Logo,喵喵作为一个90后,被委派选出能够代表他们公司的最好Logo,因为年轻人对新鲜有意思的事物十分敏感。 喵喵想了一个民主的方法,所有公司员工组成投票委员会。投票制度有点复杂:每个员工按照顺序最多给三种不同的Logo投一票。每个员工的第一种票、第二种票、第三种票分别代表3分,2分,1分。Logo的最终分数是所有员工投票后的总分数。得分最高的Logo将会被喵喵选用作为公司的Logo。如果最高分数的Logo有多个,那么获得第一种票数多的被选用。如果它们的分数和第一种票数也一样,那么第二种票多的被选用。还有类似的情况,处理情况与上述一样,如果最终还有并列的Logo,则全被选用。作为喵喵的好朋友,你能编出程序帮助他这个新手程序员顺利解决这个问题吗。

输入:

输入数据有若干组。每一组第一行有一个正整数n(1<=n<=100)表示该公司的员工总数。
接下来的n行中,每一行开始有一个整数di(1<=di<=3),表示第i的员工选择投票的Logo数
紧接着有di个不同的整数ID,表示Logo的编号(1<=ID<=1e6)。
输入将会以0为结束标志。

输出:

对于每一组样例,输出最终被选用的Logo的ID。如果有多个Logo被选用,请按照从小到大的顺序输出Logo的ID

示例输入:

4
3 5 2 1
3 12 5 2
2 1 2
3 2 1 5
2
3 3 2 1
3 2 3 1
0

示例输出:

2
2 3

提示:

参考答案(内存最优[2028]):

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int n,num,x;
ll base[]={1,1000,1000000,1000000000};
 
int main() {
    // freopen("in.txt","r",stdin);
    while (~scanf("%d",&n)&&n){
        map<int,ll> mp;
        vector<pair<int,ll> > ans;
        map<int,ll>::iterator it;
        for (int i=1;i<=n;i++) {
             scanf("%d",&num);
             for (int j=1;j<=num;j++) {
                scanf("%d",&x);
                mp[x]+=base[3]*(4-j);
                mp[x]+=base[3-j];
             }
        }
        for (it=mp.begin();it!=mp.end();++it) {
            if (ans.empty()) ans.push_back(*it);
            else {
                if (it->second == ans[0].second) ans.push_back(*it);
                else if(it->second > ans[0].second) {
                    ans.clear();
                    ans.push_back(*it);
                }
            }
        }
        printf("%d",ans[0].first);
        for (int i=1;i<ans.size();i++)
            printf(" %d",ans[i].first);
        printf("\n");
    }
    return 0;
}

参考答案(时间最优[3]):

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n,num,x;
ll base[]={1,1000,100000,100000000};

int main() {
      int n;
      while(scanf("%d",&n)!=EOF,n)
      {
            map<int ,ll > ma;
            vector < pair<int ,ll> >ve;
            rep(i,1,n)
            {
                int x;int val;
                scanf("%d",&x);
                rep(j,1,x){
                    scanf("%d",&val);
                    ma[val]+=base[3]*(4-j);
                    ma[val]+=base[3-j];
                }
            }
            for(auto it=ma.begin();it!=ma.end();it++){
             if(ve.empty())   ve.push_back(*it);
             else{
                if(it->second==ve.begin()->second)
                    ve.push_back(*it);
                else if(it->second>ve[0].second)
                {
                    ve.clear();ve.push_back(*it);
                }
             }
            }
        for(auto it=ve.begin();it!=ve.end();it++)
            printf("%d ",it->first);
            printf("\n");
      }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。