T1窗外的星

題意

一個滑動窗口，在意數軸上運動，使窗口的值最大。

思路

很明顯是求一個區間最大值，數據顯示要在O（n）的時間復雜度左右。由于窗口是個定值（作者比喻太形象）, 因此可以想到前綴和
我們一次可以想到用后端前綴和-前端前綴和來維護一個區間的最大值。
代碼如下：

#include<bits/stdc++.h>
#define N 10050
using namespace std;
short a[N],s[N];
int main(){
	int n,k,ans=0,p=0;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		a[x]=y;
		p=max(p,x);
	}
	for(int i=1;i<=p;i++){
		s[i]=s[i-1]+a[i];
	}
	for(int i=k;i<=p;i++){
		ans=max(ans,s[i]-s[i-k]);
	}
	cout<<ans;
}

系統提示：恭喜獲得10pts
觀察哪里有誤可以發現，一個點有多顆星星，注意是亮度之和而不是亮度的最大值。

代碼

#include<bits/stdc++.h>
#define N 1000050
using namespace std;
int a[N],s[N];
int main() {
	int n,k,ans=0,p=0;
	cin>>n>>k;
	if(k==0) {
		cout<<0;
		return 0;
	}
	for(int i=1; i<=n; i++) {
		int x,y;
		cin>>x>>y;
		a[x]+=y;
		p=max(p,x);
	}
	for(int i=1; i<=p; i++)s[i]=s[i-1]+a[i];
	if(k<=p)for(int i=k; i<=p; i++)ans=max(ans,s[i]-s[i-k]);
	cout<<ans;
}

T2操作系統

題意

假設該系統只有一個 CPU，每一個進程的到達時間，執行時間和運行優先級都是已知的。其中運行優先級用自然數表示，數字越大，則優先級越高。

如果一個進程到達的時候 CPU 是空閑的，則它會一直占用 CPU 直到該進程結束。除非在這個過程中，有一個比它優先級高的進程要運行。在這種情況下，這個新的（優先級更高的）進程會占用 CPU，而老的只有等待。

如果一個進程到達時，CPU 正在處理一個比它優先級高或優先級相同的進程，則這個（新到達的）進程必須等待。

一旦 CPU 空閑，如果此時有進程在等待，則選擇優先級最高的先運行。如果有多個優先級最高的進程，則選擇到達時間最早的。

思路

無需多言，模擬求解，用優先隊列維護

代碼

#include<bits/stdc++.h>
#define N 1000050
using namespace std;
struct node {
	int id, l, st, yx;
	bool operator < (const node &a) const {
		if (yx != a.yx) return yx < a.yx;
		else return l > a.l;
	}
};
long long ti;
priority_queue<node> q;
node a;
int main() {
	while (cin >> a.id >> a.l >> a.st >> a.yx) {
		while (!q.empty() && ti <= a.l) {
			if (ti + q.top().st <= a.l) {
				node x = q.top();
				q.pop();
				ti += x.st;
				cout << x.id << ' ' << ti << '\n';
			} else {
				node c = q.top();
				q.pop();
				c.st -= a.l - ti;
				q.push(c);
				ti = a.l;
				break;
			}
		}
		if (q.empty() && ti < a.l) ti = a.l;
		q.push(a);
	}
	while (!q.empty()) {
		node d = q.top();
		q.pop();
		ti += d.st;
		cout << d.id << ' ' << ti << '\n';
	}
}