3041401_ac_0ms_192k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include<stdio.h>
#include<string.h>
#define Max 101 

struct Wall
{
 int left;
 int right;
 int h;
}wall[Max];

int map[Max][Max];

void Sort(int unwall[], int num)
{
 int i, j, t;
 for(i = 0; i < num-1; i++)
  for(j = i+1; j < num; j++)
   if(wall[unwall[i]].right < wall[unwall[j]].right)
   { t = unwall[i]; unwall[i] = unwall[j]; unwall[j] = t; }
}
int main()
{
 int cas, h, k, x, y, hx;
 int minh, minl, maxh, maxl, i, j, l, d, t, num, min_num; 
 int unwall[Max];
 while(scanf("%d", &cas) != EOF){
  for(d = 0; d < cas; d++){
   memset(map, -1, sizeof(map));
   scanf("%d%d", &h, &k);
   maxh = maxl = 0;
   minh = minl = Max;
   for(i = 0; i < h; i++){
    scanf("%d%d%d%d", &x, &hx, &y, &hx);
    if(x > y) { t = x; x = y; y = t; }
    wall[i].left = x; wall[i].right = y; wall[i].h = hx;
    if(maxl < y)maxl = y;
    if(minl > x)minl = x;
    if(maxh < hx)maxh = hx;
    if(minh > hx)minh = hx;
    for(j = x; j <= y; j++){
     map[hx][j] = i;
    }
   }   
   min_num = 0;
   for(i = minl; i <= maxl; i++){
    for(num = 0, j = minh; j <= maxh; j++){
     if(map[j][i] != -1) {
      unwall[num] = map[j][i];
      num++;
     }
    }
    if(num > k){
     Sort(unwall, num);
     for(j = 0; j < num-k; j++){
      for(l = wall[unwall[j]].left; l <= wall[unwall[j]].right; l++)
       map[wall[unwall[j]].h][l] = -1;
     }
     min_num += num-k;
    }
   }
   printf("%d\n", min_num);
  }
 }
 return 0;
}