时限5s，排个序，直接做O(n^2)的DP就AC了……

最简单也最快的大概是单调队列+二分查找了（O(nlogn)）

其它的嘛~

平衡树，堆，线段树,RMQ都行，

树状数组也是可以的，但要倒过来建。

可恶心勒,整道题目恶心度100,第二个点恶心度1000

s竟然可以为0!!

我把其中一个初始化改了一下,以为差不多了,没想到还有一个初始化也要改,花了我多少时间啊,可恨的出题者!!和数据!!

下面讲讲NLOGN的伪队列优化算法

之所以叫伪,因为他维护的队列不能用O(1)输出,必须用logN时间用二分在队列搜索最优解

t表示第i个人的开始时刻，t是末时刻，c[i]是价钱

首先一定能想到Ne方程

f[t]:=min{f[k]+c[i]} (t-1

这道题中用的那个线段树就是RMQ求区间最小

先想出n^2的，线段树就是用来优化找最小值的

先要对每个人处理一下，去掉没用的头和尾

这题DP+线段树，

线段树里的KEY存的是这个范围内的费用最小值

（我怎么感觉用线段树就是为了单调队列？）

时间O(nlogE)。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

我用平衡树做的

数据不符合题目的范围 s 有可能=0！！！！

冒着封号的危险，大号小号数次提交。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 728ms

├ 测试数据 09：答案正确... 634ms

├ 测试数据 10：答案正确... 728ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2090ms

涉险过关……

写了个O(N^2)暴力DP＋堆优化，正好100行……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

这就是RP么，竟然挂在二分查找上

楼下正解

离散化可以使DP达到 N LOG N

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

树状数组就是快...

线段树+快排，nlogE

最小优先队列+快排,nlogn

强烈BS此题时间设置者..只给了1S的时间..害我CHEAT..

我觉得好象toj上的1048....

n^2写得漂亮点可以过

我是O(n*logn)的,用贪心和动规的杂交算法

谁能提供第二个数据点的数据?我不知为什么居然错了这个点

后来。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

额，为什么就AC了呢？我只是在原来的代码里加了一个不必要的条件。

原来的代码里我默认一个人的佣金大于0（题目描述：1≤ci≤214748），在新的代码里我稍微判断了一下，结果两次运行状况不同，这说明了什么？数据错误吗？

PS:严正抗议，第二个数据点不符合题目描述！

还有,为什么这个题目是"高级数据结构"里的,

貌似我的代码什么结构都没有

方程不讲了，大家自己想。

我们把存答案的数组设为d。

把每一个空闲时间当成线段，每一个线段有一个权值。i:=e->1，对于每一个I：

1.将右端点为i的线段，把它的权值+d入堆。

2.d[i]:=堆根。

3.把左端点为i的线段，删除。

d[1]为答案，O(nlogn)。

用线段树的话..把时间离散成人...也可以变成O(nlogn)

O(n^2),还是听大牛讲的。

数据恶心，还有spfa打错了查了好久
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 10000 + 5, M = 10000000 + 5;

int cnt, head[M << 1], nxt[M << 1], to[M << 1], cost[M << 1];

void AddEdge(int u, int v, int w) {
nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, cost[cnt] = w;
}

int n, s, e, d[M], c[M];
bool v[M];

bool spfa(int s,int n)
{
fill(v, v + N,0);
fill(c, c + N,0);
queue<int> que;
que.push(s);
d[s]=0;
v[s]=c[s]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
v[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int x=to[i];
if(d[x]>d[u]+cost[i])
{
d[x]=d[u]+cost[i];
if(!v[x])
{
v[x]=1;
que.push(x);
c[x]++;
if(c[x]>n) return false;
}
}
}

}
return true;
}

int main() {
scanf("%d%d%d", &n, &s, &e);
for (int i = 1; i <= n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
if (u <= e && v >= s)
AddEdge(max(u, s), min(v + 1, e + 1), w);
}
for (int i = s; i <= e + 1; i++) {
AddEdge(i + 1, i, 0);
d[i] = INT_MAX;
}
spfa(s, e - s + 2);
if (d[e + 1] == INT_MAX) d[e + 1] = -1;
printf("%d\n", d[e + 1]);
return 0;
}

RUNTIME 什么鬼！！！！！！！！

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 10001

struct PEOPLE {
int nL, nR, nC;
PEOPLE() : nL(0), nR(0), nC(0) {}
}People[MAX];
int nCount_P = 0;

struct STRUCT {
int nPre;
int nTo;
int nC;
STRUCT() : nPre(0), nTo(0), nC(0) {}
}EDGE[MAX * 100];
int head[MAX] = { 0 };
int nCount = 0;

void Add(int a, int b, int c) {
EDGE[++nCount].nTo = b;
EDGE[nCount].nC = c;
EDGE[nCount].nPre = head[a];
head[a] = nCount;
}

int n = 0, s = 0, e = 0;
int a = 0, b = 0, c = 0;

queue<int> Q;
bool IsStack[MAX] = { false };
int dis[MAX] = { 0 };
void SPFA(int nStart) {
for (int i = 0; i < MAX; i ++) dis[i] = 999999999;

Q.push(nStart);
IsStack[nStart] = true;
dis[0] = 0;

while (!Q.empty()) {
int nPoint = Q.front();
Q.pop();
IsStack[nPoint] = false;

for (int i = head[nPoint]; i != 0; i = EDGE[i].nPre) {
int nNextPoint = EDGE[i].nTo;

if (dis[nPoint] + EDGE[i].nC < dis[nNextPoint]) {
dis[nNextPoint] = dis[nPoint] + EDGE[i].nC;

if (!IsStack[nNextPoint]) {
Q.push(nNextPoint);
IsStack[nNextPoint] = true;
}
}
}
}
}

int main() {
scanf("%d %d %d", &n, &s, &e);
for (int i = 1; i <= n; i++) {
scanf("%d %d %d", &a, &b, &c);

nCount_P++;
People[nCount_P].nL = a;
People[nCount_P].nR = b;
People[nCount_P].nC = c;
}
//建图
//源点
for (int i = 1; i <= nCount_P; i++) {
if (People[i].nL == s) {
Add(0, i, 0);
}
}

for (int i = 1; i <= nCount_P; i++) {
for (int j = 1; j <= nCount_P; j++) {
if (i == j) continue;
if (People[i].nR >= People[j].nL || People[i].nR + 1 == People[j].nL) {
Add(i, j, People[i].nC);
}
}
}

//汇点
for (int i = 1; i <= nCount_P; i++) {
if (People[i].nR == e) {
Add(i, n + 1, People[i].nC);
}
}

SPFA(0);

if (dis[n + 1] >= 999999999) {
cout << -1 << endl;
}
else {
cout << dis[n + 1] << endl;
}

return 0;
}

发一个最短路SPFA的代码（其实只是最短路的思想，时间允许才能更新）。只需加一个源一个汇即可。

#include <stdio.h>

#define INF 1000000000
#define SIZE 10005

struct{
int begin, end;
} time[SIZE];
int cost[SIZE];

int dist[SIZE];
short using[SIZE];
int queue[SIZE*1000];

int minPath(int source, int sink, int numV);

int main(){
int numV, begin, end, i;

scanf("%d %d %d", &numV, &begin, &end);
for(i=0; i<numV; i++)
scanf("%d %d %d", &time[i].begin, &time[i].end, &cost[i]);
time[numV].begin = begin; //source
time[numV].end = begin;
cost[numV] = 0;
time[numV+1].begin = end+1; //sink
time[numV+1].end = end+1;
cost[numV+1] = 0;

i = minPath(numV, numV+1, numV+2);
printf("%d\n", i<INF ? i:-1);

return 0;
}
int minPath(int source, int sink, int numV){
int u, head = 0, tail = 0;
for(u=0; u<numV; u++){
using[u] = 0;
dist[u] = INF;
}
queue[tail++] = source;
dist[source] = 0;
while(head < tail){
source = queue[head];
using[source] = 0;
for(u=0; u<numV; u++){
if(time[u].begin <= time[source].end+1 && dist[u] > dist[source]+cost[u]){
dist[u] = dist[source]+cost[u];
if(!using[u]){
using[u] = 1;
queue[tail++] = u;
}
}
}
head++;
}
return dist[sink];
}