

这次笔试有点凉。
选择题问了很多早就忘干净的知识,比如,任务调度、时间片轮转、LRU、SQL、C++虚函数、C++多继承、TCP/UDP、用数组存储二叉树和最小堆、平衡二叉树旋转……
编程题也只做出 1 题。


第 2 题最简单,1 的个数减去 0 的个数,取绝对值。

第 3 题不知道什么类型的题目。
用优先级队列骗了 60%。


贪心显然不成立,从样例 1 就可以看出来。
import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] d = new int[n]; int[] p = new int[n]; for (int i = 0; i < n; i++) d[i] = in.nextInt(); for (int i = 0; i < n; i++) p[i] = in.nextInt(); PriorityQueue<Q> pq = new PriorityQueue<>(); pq.add(new Q(0, 0)); int i = 0; while (i < n) { Q q = pq.peek(); if (d[i] > q.power) { pq.poll(); pq.add(new Q(q.cost + p[i], q.power + d[i])); } else { pq.add(new Q(q.cost + p[i], q.power + d[i])); } i++; } System.out.println(pq.peek().cost); in.close(); } } class Q implements Comparable<Q> { int cost; int power; public Q(int cost, int power) { super(); this.cost = cost; this.power = power; } @Override public int compareTo(Q o) { return Integer.compare(cost, o.cost); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + cost; result = prime * result + power; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Q other = (Q) obj; if (cost != other.cost) return false; if (power != other.power) return false; return true; } }
正解是 DP。
事后问 zerol,说金币范围不是 1 就是 2,暗示了这是突破口。
第三题 要么贿赂 要么不贿赂 直接搜 2^50 不行 发现金币范围数很小 前 i 个金币数为 k 最多多少武力 搞定 |
像第三题这种 如果武力范围很小 就前 i 个武力 k 最少多少金币 |
第 1 题没做出来是不太应该,应该是签到题,贪心算法,很简单的,这个 20 分应该拿全,我只拿了 4 分。

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin>>m; cin>>n; int *a = new int[n]; for (int i = 0; i < n; ++i) { cin>>a[i]; } sort(a, a + n); if (a[0] != 1) { cout<<-1<<endl; } int sum = 1; int cnt = 1; while (sum < m) { int i = 0; for (; i < n; ++i) { if (a[i] > sum + 1) { break; } } sum += a[i - 1]; ++cnt; } cout<<cnt<<endl; }