外賣店優先級

題目分析

這一題一看N，M，T的范圍就知道不能暴力，要討巧，怎么討巧是重點。正常的思路是第一層for循環遍歷訂單（或者外賣店），第二層for循環遍歷外賣店（或者訂單），這樣可以求出每個外賣店是不是在緩存里面，但是時間復雜度是$O(N?M)=1e10>1e8$，明顯是不行的。

說一下討巧的思路，訂單我是必然要遍歷的不然你不知道哪個外賣店有單子，那么可以不遍歷外賣店嗎？這就看我們如何處理訂單了。訂單應該是一個類，包含時間ts和外賣店id，我們優先對訂單按照外賣店id排序，id相同時再按照ts排序，排序規則如下，

static class message implements Comparable<message>{//存儲訂單信息int id,t;//訂單的id和時間public message(int t, int id) {this.id = id;this.t = t;}@Overridepublic int compareTo(message o) {if(this.id != o.id) {return this.id-o.id;}else {return this.t-o.t;}			}		}

現在可以開始遍歷訂單了，在遍歷的時候我要記錄兩個值，一個是cnt用來表示當前外賣店的優先級大小，一個是flag用來表示當前外賣店是否被放在緩存里面。一個是ans表示我知道的在緩存里面的外賣店的數量。

int flag = 0;//表示是否在優先級緩存中，在的flag=1，
int ans = 0;//記錄答案
int cnt = 2;//表示外賣店的優先級大小

對于當前訂單me[i]，我要知道前一個訂單me[i-1]是否和他是同一個外賣店，如果是，那么說明我此時把me[i-1].id的外賣店的單子都遍歷完了，此時我要確定他是不是在緩存里面。兩步確定法，一是確定flag是否等于1，二十確定從最后一個單子的時間到時間t內，是否會使他的優先級減少到小于等于3的情況。

if(me[i].id!=me[i-1].id) {//如果變成下一個外賣店了，就要檢查剛剛那個外賣店是不是在緩存中的//falg=1并且到達t時，沒有小于等于3if(flag == 1 && (cnt - (t - me[i-1].t) > 3 )) {ans++;}cnt = 2;//此時是me[i].id有單子，那么cnt初始值應該是2flag = 0;//重置flag
}

否則的話，先求從上一個訂單到當前這個訂單，外賣店的優先級降低了多少，也就是經歷的時間。那么這里為什么是int diff = me[i].t - me[i-1].t - 1;呢？舉個例子，假設當前的時間是4，前一個的時間是2，那么中間沒有訂單的時間就是ts=3時，因此優先級應該降低1，那么也就是4-2-1。但是注意，如果出現了當前的時間是4，前一個的時間也是4，會出現4-4-1=-1的情況，但是實際此時應該優先級降低0，所以會有if(diff == -1) diff = 0;。那么這個if(cnt <= 3)一定要在cnt += 2;之前判斷，舉個例子，假設外賣店的當前優先級是4，那么diff=2，4減2等于2，此時應該被移出優先級緩存的，但是如果在判斷之前我先給他加了2，那么此時2+2=4>3，他就不會移出優先級緩存，造成結果錯誤。

else {int diff = me[i].t - me[i-1].t - 1;//優先級降低了多少 me[i].t=1  me[i-1].t=1if(diff == -1) diff =  0;cnt = Math.max(0, cnt - diff);//如果優先級降低到了負數，那么他就是0if(cnt <= 3) flag = 0;//如果小于等于3會被移出緩存cnt += 2;//出現了訂單，優先級加2.if(cnt > 5) flag = 1;//如果大于5會被加入緩存
}

注意，最后一個外賣店，我沒有判斷它是否在緩存里面，所以for循環結束后要判斷

//對最后一個訂單/最后一個外賣店進行判斷
if(flag == 1 && (cnt - (t - me[m-1].t) > 3 )) {ans++;
}
System.out.println(ans);

題目代碼

import java.util.Arrays;
import java.util.Scanner;
public class Main{static class message implements Comparable<message>{//存儲訂單信息int id,t;//訂單的id和時間public message(int t, int id) {this.id = id;this.t = t;}@Overridepublic int compareTo(message o) {if(this.id != o.id) {return this.id-o.id;}else {return this.t-o.t;}			}		}
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int t = scanner.nextInt();message[] me = new message[m];for (int i = 0; i < me.length; i++) {me[i] =new message(scanner.nextInt(), scanner.nextInt());}Arrays.sort(me);int flag = 0;//表示是否在優先級緩存中，在的flag=1，int ans = 0;//記錄答案int cnt = 2;//表示外賣店的優先級大小for (int i = 1; i < m; i++) {if(me[i].id!=me[i-1].id) {//如果變成下一個外賣店了，就要檢查剛剛那個外賣店是不是在緩存中的//falg=1并且到達t時，沒有小于等于3if(flag == 1 && (cnt - (t - me[i-1].t) > 3 )) {ans++;}cnt = 2;//此時是me[i].id有單子，那么cnt初始值應該是2flag = 0;//重置flag}else {int diff = me[i].t - me[i-1].t - 1;//優先級降低了多少 me[i].t=1  me[i-1].t=1if(diff == -1) diff =  0;cnt = Math.max(0, cnt - diff);if(cnt <= 3) flag = 0;cnt += 2;if(cnt > 5) flag = 1;}}//對最后一個訂單/最后一個外賣店進行判斷//講日期模擬器的時候，whie循環結束后，也得有一個if語句，對最后一個日期進行檢查if(flag == 1 && (cnt - (t - me[m-1].t) > 3 )) {ans++;}System.out.println(ans);
}
}