腾讯2018秋招笔试真题（1） - 好文

腾讯2018秋招笔试真题

小Q的歌单

【题目描述】小 Q 有 X 首长度为 A 的不同的歌和 Y 首长度为 B 的不同的歌，现在小 Q 想用这些歌组成一个
总长度正好为 K 的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，
请问有多少种组成歌单的方法。
输入描述：
每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度 K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度 A(A<=10)和数量 X(X<=100)以及歌的第二种长度
B(B<=10)和数量 Y(Y<=100)。保证 A 不等于 B。
输出描述：
输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对 1000000007 取模的结果。
输入示例：
5
2 3 3 3
输出示例：
9

解题思路：
x首歌里面取i首，每首歌长度为A
y首歌里面取j首歌，每首歌长度为B
加起来长度为K
i*A + j*B = K
有多少种方式，可看成排列组合来做
类比（有一个盒子中装有红球x个，白球y个，取出红球得A分，取出白球得B分，从中任意取使得得到的分数为K分，有多少种方法）
满足条件
0 <= i <= x
j = (K-i*A)/B <= y
(K-i*A)%B = 0
import java.util.Scanner; public class Main01 { public static void main
(String[] args) {int[][] c = new int[101][101];//组合排列 Scanner in = new
Scanner(System.in);int K = in.nextInt(); //歌单总长度 int A = in.nextInt(); //第一种歌的长度
int x = in.nextInt(); //第一种歌的数量 int B = in.nextInt(); //第二种歌的长度 int y =
in.nextInt();//第二种歌的数量 //初始化数组c 第一个参数是下标，第二个参数是上标 c[0][0] = 1; for(int i = 1;
i < c.length; i++) { c[i][0] = 1; for(int j = 1; j < c[0].length; j++) {
c[i][j] = (c[i -1][j - 1] + c[i - 1][j]) % 1000000007; } } int res = 0; for(int
i =0; i <= x; i++) { //i首长度为A的歌 if(i * A <= K && (K - i * A) % B == 0 && (K - i
* A) / B <= y) { res = (res + ((c[x][i] * c[y][(K-(i * A)) / B])) %1000000007 )
%1000000007; } } System.out.println(res); } }
安排机器

【题目描述】小 Q 的公司最近接到 m 个任务, 第 i 个任务需要 xi 的时间去完成, 难度等级为 yi。
小 Q 拥有 n 台机器, 每台机器最长工作时间 zi, 机器等级 wi。
对于一个任务,它只能交由一台机器来完成, 如果安排给它的机器的最长工作时间小于任务需要的时间,
则不能完成,如果完成这个任务将获得 200 * xi + 3 * yi 收益。
对于一台机器,它一天只能完成一个任务, 如果它的机器等级小于安排给它的任务难度等级, 则不能完成。
小 Q 想在今天尽可能的去完成任务, 即完成的任务数量最大。如果有多种安排方案,小 Q 还想找到收益最大
的那个方案。小 Q 需要你来帮助他计算一下。
输入描述：
输入包括 N + M + 1 行,
输入的第一行为两个正整数 n 和 m(1 <= n, m <= 100000), 表示机器的数量和任务的数量。
接下来 n 行,每行两个整数 zi 和 wi(0 < zi < 1000, 0 <= wi <= 100), 表示每台机器的最大工作时间和
机器等级。
接下来的 m 行,每行两个整数 xi 和 yi(0 < xi < 1000, 0 <= yi<= 100), 表示每个任务需要的完成时间和
任务的难度等级。
输出描述：
输出两个整数, 分别表示最大能完成的任务数量和获取的收益。
输入示例：
1 2
100 3
100 2
100 1
输出示例：
1 20006

解题思路：
对2个队列分别进行排序
排序规则为：先按time从大到小排，再按level从大到小排（因为时间占收益的比重比较大，所以优先time排序）
然后处理任务进行匹配
匹配规则为：选择机器时间>=任务时间，机器优先级与任务优先级最接近的
import java.util.ArrayList; import java.util.Collections; import
java.util.List;import java.util.Scanner; class Task implements Comparable { int
time;//时间 int level; //等级 public Task(int time, int level) { super(); this.time
= time;this.level = level; } @Override public int compareTo(Object o) { Task t
= (Task)o;if(this.time > t.time) { return -1;//返回-1，表示当前对象在前，即从大到小排序 } else if(
this.time < t.time) { return 1; } else { if(this.level > t.level) { return -1; }
else { return 1; } } } } public class Main02 { public static void main(String[]
args) { List<Task> machine =new ArrayList<Task>(); List<Task> job = new
ArrayList<Task>(); Scanner in =new Scanner(System.in); int n = in.nextInt(); int
m = in.nextInt();for(int i = 0; i < n; i++) { Task t = new Task(in.nextInt(),
in.nextInt()); machine.add(t); }for(int j = 0; j < m; j++) { Task t = new
Task(in.nextInt(), in.nextInt()); job.add(t); } Collections.sort(machine);
Collections.sort(job);int count = 0; int sum = 0; int[] mark = new int[101]; for
(int i = 0, j = 0; i < m; i++) {//m项任务 while(j < n && machine.get(j).time >=
job.get(i).time) {//由于从大到小排序，所以如果machine.time比位于前面的job.time大，那也比后面的大，后面只需要比较优先级
mark[machine.get(j).level]++; j++; }for(int k = job.get(i).level; k <= 100;
k++) {if(mark[k] != 0) {//mark[k]=1时表示优先级为k的机器可以处理该任务 count++; sum += 200 *
job.get(i).time +3 * job.get(i).level; mark[k]--; break; } } }
System.out.println(count +" " + sum); } }

热门工具换一换