• 2018-01-05
• 0
• 0

## Problem:

 Time Limit: 2000MS Memory Limit: 65536K Special Judge

Description

There are n preemptive jobs to be processed on a single machine. Each job j has a processing time pj and deadline dj. Preemptive constrains are specified by oriented graph without cycles. Arc (i,j) in this graph means that job i has to be processed before job j. A solution is specified by a sequence of the jobs. For any solution the completion time Cj is easily determined.

The objective is to find the optimal solution in order to minimize

max{Cj-dj, 0}.

Input

The first line contains a single integer n, 1 ≤ n ≤ 50000. Each of the next n lines contains two integers pj and dj, 0 ≤ pj ≤ 1000, 0 ≤ dj ≤ 1000000, separated by one or more spaces. Line n+2 contains an integer m (number of arcs), 0 ≤ m ≤ 10*n. Each of the next m lines contains two integers i and j, 1 ≤ ij ≤ n.

Output

Each of the n lines contains integer i (number of job in the optimal sequence).

Sample Input

```2
4 1
4 0
1
1 2```

Sample Output

```1
2```

Source

Northeastern Europe 2003, Western Subregion

## Solution:

【贪心证明】

• 先加工 i：max{T + p[i] - d[i], T + p[i] + p[j] - d[j]} …… i)
• 先加工 j：max{T + p[j] - d[j], T + p[j] + p[i] - d[i]} …… ii)

S = T + p[i] + p[j]，则

• i) 可化为：max{S - p[j] - d[i], S - d[j]} = S + min{p[j] + d[i], d[j]}
• ii) 可化为：max{S - p[i] - d[j], S - d[i]} = S + min{p[i] + d[j], d[i]} = S + d[i]

【华丽丽的 Q.E.D.】

## Code: O(NlogN+M) [1564K, 313MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;

int n, m;

struct Job{
int p, d;
} job[50005];

struct Edge{
int np;
Edge *nxt;
};

struct Graph{
Edge *V[50005], E[500005];
int tope;

inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}
} G;

int indeg[50005];
priority_queue<PII, vector<PII>, greater<PII> > deg0;

int main(){
scanf("%d", &n);
for(register int i = 1; i <= n; i++) scanf("%d%d", &job[i].p, &job[i].d);
scanf("%d", &m);
for(register int i = 1; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
}
for(register int i = 1; i <= n; i++)
if(!indeg[i]) deg0.push(PII(job[i].d, i));
while(!deg0.empty()){
int u = deg0.top().second; deg0.pop();
printf("%d\n", u);
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(!--indeg[ne->np]) deg0.push(PII(job[ne->np].d, ne->np));
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai