|
|
這題不懂做，一開始想了一個動態(tài)規(guī)劃的方法，復(fù)雜度很高。估計得幾百ms。
看status，覺得肯定有很低復(fù)雜度的方法。
然后看了 Discuss ，看到某位大牛說的貪心方法，頓時恍然大悟，嗎的實在太牛逼了。
這位大牛的解法如下：
想象自己是一個黑一日游的司機：
1.如果有乘客要上車，那么就讓他上，收錢！
2.如果超載了，把距目的地最遠的幾個乘客踢下去，退錢。
3.行駛到下一站
照著這個方法編碼，一開始速度很慢，后來改成用一個隊列來維護車上的乘客，速度就很快了，還飚上榜了。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 10032
#define MAX_K 50032
  struct slot_node  {
 int end, cap;
struct slot_node *next;
 };
struct stat_node {
int idx[MAX_N], cnt[MAX_N], head, tail, tot;
};
struct slot_node *start[2][MAX_N], slots[MAX_K*2];
struct stat_node stat[2];
int K, N, C, left, right, slots_cnt, ans;
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void ins(int a, int b, int c, int d)
{
struct slot_node *t;
if (b > right)
right = b;
if (a < left)
left = a;
t = &slots[slots_cnt++];
t->next = start[d][a];
t->end = b;
t->cap = c;
start[d][a] = t;
}
inline void off(int d, int i)
{
struct stat_node *t = &stat[d];
if (t->head == t->tail || t->idx[t->head] != i)
return ;
ans += t->cnt[t->head];
t->tot -= t->cnt[t->head];
t->head++;
}
inline void del(struct stat_node *t)
{
int c;
  while (t->tot > C) {
c = min(t->tot - C, t->cnt[t->tail - 1]);
t->cnt[t->tail - 1] -= c;
t->tot -= c;
if (!t->cnt[t->tail - 1])
t->tail--;
 }
}
inline void add(struct stat_node *t, int cap, int end)
{
int i, j;
t->tot += cap;
for (i = t->tail - 1; i >= t->head; i--) {
if (t->idx[i] == end) {
t->cnt[i] += cap;
return ;
} else if (t->idx[i] < end)
break;
}
i++;
t->tail++;
for (j = t->tail - 1; j > i; j--) {
t->idx[j] = t->idx[j - 1];
t->cnt[j] = t->cnt[j - 1];
}
t->idx[i] = end;
t->cnt[i] = cap;
}
inline void on(int d, int i)
{
struct slot_node *s;
struct stat_node *t = &stat[d];
for (s = start[d][i]; s; s = s->next)
add(t, s->cap, s->end);
del(t);
}
int main()
{
int i, a, b, c;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &K, &N, &C);
left = N;
for (i = 0; i < K; i++) {
scanf("%d%d%d", &a, &b, &c);
if (a > b)
ins(N - a, N - b, c, 1);
else
ins(a, b, c, 0);
}
for (i = left; i <= right; i++) {
off(0, i);
off(1, i);
on(0, i);
on(1, i);
}
printf("%d\n", ans);
return 0;
}
|