调色盘 (3维k点最小最远点对-容斥原理）

调色盘(pastele)

题目描述

Albus得到了一份礼物：来自Polaris的水彩油墨包。

Polaris的油墨包里面有N个颜色，现在Albus打算选其中的K种来作一幅风景画。

既然是风景画，颜色就不能太突兀。因此Albus进行了如下的定义：

每个颜色由三个属性刻画：R[i],G[i],B[i]。

两个颜色的“距离”指它们三个属性的最大差值，也就是Max(|Ri-Rj|,|Gi-Gj|,|Bi-Bj|)。

而K个颜色的距离，指的是其中任意两个颜色的最大距离。

你的任务是求出可能的最小距离。

输入

第一行两个整数N和K。

接下来N行，每行三个整数R[i],G[i],B[i]。

输出

可能的最小距离。

样例输入

5 3

6 6 4

6 2 7

3 1 3

4 1 5

6 2 6

样例输出

2

解释

选1,4,5三个颜色。

数据范围

对于10%的数据，N<=10

对于50%的数据，0<=Ri,Gi,Bi<=20，2<=K<=N<=100

对于80%的数据，0<=Ri,Gi,Bi<=50,2<=K<=N<=10000

对于100%的数据，2<=K<=N<=100000,0<=Ri,Gi,Bi<=150

a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

容斥原理

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (150+10)
#define MAXX (151)
int n,k,a[MAXN][MAXN][MAXN]={0},c[MAXN][MAXN][MAXN]={0};
int Node_count(int x,int y,int z,int l)
{
  if (z-l<0||y-l<0||z-l<0) return 0;
  return c[x][y][z]+c[x-l][y-l][z]+c[x][y-l][z-l]+c[x-l][y][z-l]-c[x-l][y][z]-c[x][y-l][z]-c[x][y][z-l]-c[x-l][y-l][z-l];
    
}
int main()
{
  freopen("pastele.in","r",stdin);
  freopen("pastele.out","w",stdout);
  
  scanf("%d%d",&n,&k);
  for (int i=1;i<=n;i++)
  {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    a[x+1][y+1][z+1]++;
  }
  
  
  /*
    a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
    c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

  */
  
  for (int x=1;x<=MAXX;x++)
    for (int y=1;y<=MAXX;y++)
      for (int z=1;z<=MAXX;z++)
        c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);
  
  /*
  for (int i=1;i<=10;i++)
  for (int j=1;j<=10;j++)
  for (int k=1;k<=10;k++)
    if (c[i][j][k]) cout<<i<<' '<<j<<' '<<k<<' '<<c[i][j][k]<<endl;
  cout<<Node_count(6,6,6,6);
  */
  
  int ans=MAXX;//成立 区间  (0 ,MAXX] 
  for (int x=MAXX;x>=1;x--)
    for (int y=MAXX;y>=1;y--)
      for (int z=MAXX;z>=1;z--)
      {      
        if (ans&&k<=Node_count(x,y,z,ans)) ans--;
      }
  cout<<ans<<endl;
  
  
//  while (1);
  return 0;
}