一、一道繁琐的大模拟
N个产品经理，M个程序员，P个需求。N个产品经理向M个程序员提出P个需求。
每个需求用四元组表示：产品经理ID（谁提出的） 提出时间 优先级（数字越大优先级越高） 需求开发时长
每个产品经理对于自己的需求按照：优先级从高到低、开发时长从短到厂、提出时间 从早到晚排序
每个程序员每次从产品经理最想做的需求里面挑选用时最短（如果时间相同优先做PM编号较小的需求）
求每个需求的完成时间。
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
class Idea {
int pm, think, use, pri, index;
int over;
Idea(int pm, int think, int pri, int use, int index) {
this.pm = pm;
this.think = think;
this.use = use;
this.pri = pri;
this.index = index;
}
@Override
public String toString() {
return "pm:" + pm + " think:" + think + " use" + use + " pri:" + pri;
}
}
class Pm {
PriorityQueue<Idea> ideas = new PriorityQueue<>((x, y) -> {
if (x.pri != y.pri) return -x.pri + y.pri;
if (x.use != y.use) return x.use - y.use;
return x.think - y.think;
});
boolean want(Idea i) {
return ideas.peek() == i;
}
}
class Programmer {
int time = 0;
}
Main() {
Scanner cin = new Scanner(System.in);
int PMCount = cin.nextInt(), ProgrammerCouunt = cin.nextInt(), IdeaCount = cin.nextInt();
Idea[] a = new Idea[IdeaCount];
Pm pms[] = new Pm[PMCount + 1];
for (int i = 0; i <= PMCount; i++) {
pms[i] = new Pm();
}
for (int i = 0; i < IdeaCount; i++) {
a[i] = new Idea(cin.nextInt(), cin.nextInt(), cin.nextInt(), cin.nextInt(), i);
}
PriorityQueue<Programmer> consumer = new PriorityQueue<>(Comparator.comparing(x -> x.time));
Arrays.sort(a, Comparator.comparingInt(x -> x.think));
int ai = 0;
PriorityQueue<Idea> producer = new PriorityQueue<>((x, y) -> {
if (x.use != y.use) return x.use - y.use;
return x.pm - y.pm;
});
for (int i = 0; i < ProgrammerCouunt; i++) consumer.add(new Programmer());
while (!producer.isEmpty() || ai < a.length) {
Programmer worker = consumer.poll();
if (producer.isEmpty()) {
worker.time = Math.max(a[ai].think, worker.time);
}
while (ai < a.length && a[ai].think <= worker.time) {
Idea task = a[ai++];
pms[task.pm].ideas.add(task);
producer.add(task);
}
Idea idea = producer.poll();
Pm pm = pms[idea.pm];
if (pm.want(idea)) {//如果当前idea是pm最想做的idea
pm.ideas.poll();//pm完成了这个任务
if (!pm.ideas.isEmpty()) producer.add(pm.ideas.peek());
worker.time = idea.over = Math.max(worker.time, idea.think) + idea.use;
// System.out.println("idea " + idea + " " + worker.time);
}
consumer.add(worker);
}
Arrays.sort(a, Comparator.comparingInt(x -> x.index));
for (Idea i : a) {
System.out.println(i.over);
}
}
public static void main(String[] args) {
new Main();
}
}
二、单调栈的变形应用
给定数组a[N]，它有许多区间，求s=min(a[l:r]) imes sum(a[l:r])的最大值。a[N]中全为正整数。
sum(a[l:r])可以快速通过前缀和求出，因为要求s的最大值，所以区间[l:r]应该尽量大。但是又不能太大，因为太大的话，会使得min(a[l:r])很小。
对于a中的每个元素a[i]，在保证a[i]为最小值得情况下，扩张左区间和右区间。问题转化为快速求解a[i]左右第一个比它小的元素。
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn = 5 * 1e5;
int n;
int a[maxn];
int s[maxn];
int lef[maxn], righ[maxn];//每个数字左边比我小的和右边比我小的
int getsum(int f, int t) {
if (t == 0)return s[f];
return s[t] - s[f - 1];
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)scanf("%d", a + i);
int nows = 0;
for (int i = 0; i < n; i++) {
s[i] = nows + a[i];
nows += a[i];
}
stack<int>sta;
for (int i = 0; i < n; i++) {
while (!sta.empty()) {
int topIndex = sta.top();
int value = a[topIndex];
if (value > a[i]) {
sta.pop();
righ[topIndex] = i - 1;
}
else {
break;
}
}
int last = (sta.empty() ? 0 : sta.top() + 1);
lef[i] = last;
sta.push(i);
}
while (!sta.empty()) {
int topIndex = sta.top();
sta.pop();
righ[topIndex] = n - 1;
}
long long s = 0;
for (int i = 0; i < n; i++) {
s = max(s, getsum(lef[i], righ[i])*(long long)a[i]);
}
cout << s << endl;
return 0;
}
三、求边界点
平面直角坐标系第一象限中包含一堆整数点，请找到全部满足以下条件的点：(x,y)的左方、上方一个点也没有。
这道题简单的排序就能通过，但是因为数据量太大，用Java很容易超时，用C++ cin都会超时，必须用scanf才可以。
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 5 * 1e5;
int n;
struct Point {
int x, y;
}a[maxn];
int b[maxn];
int bi;
bool com(const Point&one, const Point&two) {
if (one.x != two.x)return one.x<two.x;
else return one.y < two.y;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d%d", &a[i].x, &a[i].y);
}
sort(a, a + n, com);
bi = 0;
for (int i = 0; i < n; i++) {
if (i == n || a[i].x != a[i + 1].x) {
b[bi++] = i;
}
}
int ma = 0;
for (int i = bi - 1; i >= 0; i--) {
int ind = b[i];
if (ma > a[ind].y) {
b[i] = -1;
}
ma = max(ma, a[ind].y);
}
for (int i = 0; i < bi; i++) {
if (b[i] != -1) {
int ind = b[i];
cout << a[ind].x << " " << a[ind].y << endl;
}
}
return 0;
}