Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 优先队列 0ms（另外这题用得着65536K？）

Posted by KatrineYang at 2016-08-29 23:55:04 on Problem 1230 and last updated at 2016-08-29 23:56:04
```#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

inline int mx(int a, int b){return (a>b)? a : b;}
inline int mn(int a, int b){return (a<b)? a : b;}

struct wall{
int start, end;
}walls[110];

bool operator<(const wall &w1, const wall &w2){
return w1.end < w2.end;
}

bool compare(const wall &w1, const wall &w2){
return w1.start < w2.start;
}

int main() {
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ii++){
int N, K;
int block[110] = {0};
scanf("%d%d", &N, &K);
int start, end, fei;
for(int i = 0; i < N; i++){
scanf("%d%d%d%d", &start, &fei, &end, &fei);
if(start > end){
int temp = start;
start = end;
end = temp;
}
walls[i].start = start, walls[i].end = end;
}
walls[N].start = -1, walls[N].end = -1;
sort(walls, walls+N, compare);
priority_queue<wall> pq;
int startP = walls[0].start;
int i = 0;
int qd = 0;
while(i < N){
while(walls[i].start == startP){
pq.push(walls[i]);
for(int j = walls[i].start; j <= walls[i].end; j++) block[j] ++;
i++;
}
int cha = block[startP] - K;
while(cha > 0){
wall w = pq.top();
pq.pop();
for(int j = w.start; j <= w.end; j++) block[j]--;
cha--;
qd++;
}
startP = walls[i].start;
}
printf("%d\n", qd);
}
return 0;
}
```

Followed by: