t1-Supermarket 超市利润
题目大意
给定n个商品，每个商品有利润pi和过期时间di。每天只能卖一个商品，过期商品不能卖。求如何安排每天卖的商品可以使收益最大。
分析
一开始打了一个复杂度跑不满\(n^2\)的暴力发现T掉了，就换成了\(nlogn\)的算法，但是依旧是T掉了，而且T飞掉了，看到洛谷里有人发帖子说只能用cin才A掉了。
首先，很明显最优的是一直在卖东西，那么可以将所有的已经当前决定是卖掉的物品放入一个小根堆中。
我们先将这些物品按照日期从小到大排序
分成3种情况讨论：
- 如果当前的过期日期=堆中元素个数，说明在过期最后一天不能卖这个物品了，那么就把堆顶取出，弹入较大的。
- 如果当前的过期日期<堆中元素个数，说明可以直接卖掉，那么直接弹入堆中。
- 如果当前的过期日期>堆中元素个数，不存在这种情况，直接跳过
每一次操作后都要维护堆。
ps.前辈的经验，不要用while (scanf("%d", &n)!=EOF)，T到自己怀疑人生，而且自己学校的oj还有手写堆，更加怀疑人生。
ac代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define N 10005
#pragma GCC optimize(2)
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') fl = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= fl;
}
struct node {
int p, d;
inline bool operator <(const node &rhs) const {
return d < rhs.d;
}
}a[N];
int n, ans;
bool vis[N];
struct Heap {
int heap[N], tot;
inline void up(int u) {
while (u > 1) {
if (heap[u] < heap[u >> 1]) {
swap(heap[u], heap[u >> 1]);
u >>= 1;
}
else break;
}
}
inline void insert(int v) {
heap[++ tot] = v;
up(tot);
}
inline void down(int u) {
int s = u << 1;
while (s <= tot) {
if (s < tot && heap[s] > heap[s + 1]) s ++;
if (heap[s] < heap[u]) {
swap(heap[s], heap[u]);
u = s;
s = u << 1;
}
else break;
}
}
inline void pop() {
heap[1] = heap[tot --];
down(1);
}
inline int get_top() {
return heap[1];
}
inline void clear() {
memset(heap, 0, sizeof(heap));
tot = 0;
}
}heap;
int main() {
while (cin>> n) {
heap.clear();
ans = 0;
for (register int i = 1; i <= n; i ++) {
read(a[i].p); read(a[i].d);
}
sort(a + 1, a + 1 + n);
for (register int i = 1; i <= n; i ++) {
if (a[i].d == heap.tot) {
if (a[i].p > heap.get_top()) {
heap.pop();
heap.insert(a[i].p);
}
}
else if (a[i].d > heap.tot) {
heap.insert(a[i].p);
}
}
for (register int i = 1; i <= heap.tot; i ++)
ans += heap.heap[i];
printf("%d\n", ans);
}
return 0;
}t2-Sequence
题目大意
给你m个长度为n的数列，让你从m个队列中每一个数列中取出一个数，求出字典序的第n小。