[数据结构与算法]L2-021 点赞狂魔 - java

L2-021 点赞狂魔

时间限制
200 ms
内存限制
64 MB

题目描述：

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：
输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name $K$ $F_1$ ? $F_K$ ”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，$F_i$ （i=1,?,K）是特性标签的编号，我们将所有特性标签从 1 到 $10^7$ 编号。数字间以空格分隔。

输出格式：
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：
5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14
输出样例：
jack chris john

给定n个人的点赞情况 求出每个人点赞的不同标签的数量的前3名

如果有并列，则输出标签出现次数平均值最小的那个

还有要是人数不足3人，则用-补齐缺失

emmmmmmm

利用set将给定第i个人的点赞去重

然后对象排序 排除指定的顺序

排序的时候
按照 不同点赞的数 从大到小 排序
如果有相同 那么按标签出现次数平均值最小的那个

出现次数平均值 = $\frac{不同点赞的数}{点赞的总数}$
所以平均值最小的那个 也就是总数最多的一个

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main
{

	static class edge implements Comparable<edge>
	{
		String name;
		int zan, zong;

		public edge(String name, int zan, int zong)
		{
			this.name = name;
			this.zan = zan;
			this.zong = zong;
		}

		@Override
		public int compareTo(edge other)
		{
			if (other.zan != this.zan)
				return other.zan - this.zan;
			return this.zong - other.zong;
		}
	}

	public static void main(String[] args) throws IOException
	{
		int n = sc.nextInt();
		ArrayList<edge> ar = new ArrayList<edge>();
		for (int i = 1; i <= n; i++)
		{
			String name = sc.next();
			int k = sc.nextInt();

			TreeSet<Integer> tr = new TreeSet<Integer>();
			for (int j = 1; j <= k; j++)
			{
				int f = sc.nextInt();
				tr.add(f);
			}
			ar.add(new edge(name, tr.size(), k));
		}
		Collections.sort(ar);
		for (int i = 0; i < Math.min(n, 3); i++)
		{
			if (i != 0)
				out.print(" ");
			out.print(ar.get(i).name);
		}
		for (int i = n; i < 3; i++)
			out.print(" -");

		out.flush();
		out.close();
	}

	static InputReader sc = new InputReader();
	static PrintWriter out = new PrintWriter(System.out);

	static class InputReader
	{
		private InputStream inputStream = System.in;
		private byte[] buf = new byte[100000];
		private int curChar;
		private int numChars;

		public int getchar()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = inputStream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt()
		{
			int a = 0, b = 1;
			int c = getchar();
			while (c < '0' || c > '9')
			{
				if (c == '-')
				{
					b = -1;
				}
				c = getchar();
			}
			while (c >= '0' && c <= '9')
			{
				a = (a << 1) + (a << 3) + (c ^ 48);
				c = getchar();
			}
			return a * b;
		}

		public String next()
		{
			int c = getchar();
			while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1)
			{
				c = getchar();
			}
			StringBuilder res = new StringBuilder();
			do
			{
				if (Character.isValidCodePoint(c))
					res.appendCodePoint(c);
				c = getchar();
			} while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1));
			return res.toString();
		}
	}

}

TreeSet

对象数组排序

对象排序

对象排序

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

闪现

阅读世界，共赴山海

423全民读书节，邀你共读