这个题是第十届也就是这次比赛好像是第六题还是第七题,是一道模拟外卖系统的题目,题目描述很简单,有外卖就加分,没有减分,分数大进缓存系统,少了出系统,模拟就可以,但是数据量有点大,单单的暴力模拟最后的满数据过不了。
优化方法是将相同订单批次处理。
AC代码:
import java.io.*;
import java.util.Arrays;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
static int n, m, t;
static int score[], last[]; //last[] 记录上次订单时间
static boolean inlist[]; //inlist[]记录是否在优先缓存中
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
t = Integer.parseInt(s[2]);
Point p[] = new Point[m];
score = new int[n + 1];
last = new int[n + 1];
inlist = new boolean[n + 1];
for (int i = 0; i < m; i++) {
s = br.readLine().split(" ");
p[i] = new Point(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
}
Arrays.sort(p);
for (int i = 0; i < m; ) {
int j = i;
while (j < m && p[i].getTime() == p[j].getTime() && p[i].getId() == p[j].getId()) j++;
int time = p[i].getTime(), id = p[i].getId(), cnt = j - i;
i = j;
score[id] -= time - last[id] - 1;
if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) inlist[id] = false;
score[id] += cnt * 2;
if (score[id] > 5) inlist[id] = true;
last[id] = time;
}
for (int i = 1; i <= n; i++) {
if (last[i] < t) {
score[i] -= t - last[i];
if (score[i] <= 3) inlist[i] = false;
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (inlist[i]) res++;
}
pw.print(res);
pw.flush();
pw.close();
br.close();
}
}
class Point implements Comparable<Point> {
private int time;
private int id;
public int getTime() {
return time;
}
public int getId() {
return id;
}
public Point(int time, int id) {
this.time = time;
this.id = id;
}
@Override
public int compareTo(Point p) {
if (this.getTime() == p.getTime()) return this.getId() - p.getId();
return this.getTime() - p.getTime();
}
}
这边给出暴力的模拟代码 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
static int n, m, t;
static int p[];
static boolean inlist[], ifNew[];
static PriorityQueue<Time> queue = new PriorityQueue<>(new Comparator<Time>() {
@Override
public int compare(Time time, Time t1) {
return time.getMin() - t1.getMin();
}
});
public static void main(String[] args) throws NumberFormatException, IOException {
String s[] = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
t = Integer.parseInt(s[2]);
inlist = new boolean[n + 1];
ifNew = new boolean[n + 1];
p = new int[n + 1];
for (int i = 0; i < m; i++) {
s = br.readLine().split(" ");
queue.offer(new Time(Integer.parseInt(s[0]), Integer.parseInt(s[1])));
}
for (int i = 1; i <= t; i++) {
if (i > m && i == t) {
int sum = 0;
for (int j = 1; j <= n; j++) {
if (inlist[j]) sum++;
}
pw.print(sum);
}
if (i > m) {
for (int k = 1; k <= n; k++) {
if (p[k] > 0) p[k]--;
}
continue;
}
while (!queue.isEmpty()) {
Time temp = queue.peek();
if (temp.getMin() == i) {
int num = temp.getNum();
p[num] += 2;
ifNew[num] = true;
} else break;
queue.poll();
}
for (int j = 1; j <= n; j++) {
if (!ifNew[j]) {
if (p[j] > 0)
p[j]--;
}
if (p[j] > 5) inlist[j] = true;
if (p[j] <= 3) inlist[j] = false;
}
Arrays.fill(ifNew, false);
if (i == t) {
int sum = 0;
for (int j = 1; j <= n; j++) {
if (inlist[j]) sum++;
}
pw.print(sum);
break;
}
}
pw.flush();
pw.close();
br.close();
}
}
class Time {
int min;
int num;
public int getMin() {
return min;
}
public void setMin(int min) {
this.min = min;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public Time(int min, int num) {
this.min = min;
this.num = num;
}
}