http://codeforces.com/contest/846/problem/D
二分答案
适合于：
判断在t时候第一次成立
哪个状态是最小代价
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define E 2.7182818284 23 const ll mod=1e9+7;//998244353 24 const int maxn=5e2+10; 25 26 struct node 27 { 28 int x,y,t; 29 }f[maxn*maxn]; 30 31 int K,s,t,a[maxn][maxn],tot[maxn][maxn]={0}; 32 33 int cmp(node a,node b) 34 { 35 return a.t<b.t; 36 } 37 38 bool judge() 39 { 40 int i,j; 41 for (i=K;i<=s;i++) 42 for (j=K;j<=t;j++) 43 if (tot[i][j]-tot[i-K][j]-tot[i][j-K]+tot[i-K][j-K]==K*K) 44 return 1; 45 return 0; 46 } 47 48 int main() 49 { 50 int q,i,j,l,r,m; 51 scanf("%d%d%d%d",&s,&t,&K,&q); 52 for (i=1;i<=q;i++) 53 scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].t); 54 55 sort(f+1,f+q+1,cmp); 56 57 l=1,r=q; 58 while (l<=r) 59 { 60 memset(a,0,sizeof(a)); 61 m=(l+r)>>1; 62 63 for (i=1;i<=m;i++) 64 a[f[i].x][f[i].y]=1; 65 for (i=1;i<=s;i++) 66 for (j=1;j<=t;j++) 67 tot[i][j]=tot[i-1][j]+tot[i][j-1]-tot[i-1][j-1]+a[i][j]; 68 if (judge()) 69 r=m-1; 70 else 71 l=m+1; 72 } 73 if (l==q+1) 74 printf("-1"); 75 else 76 printf("%d",f[l].t); 77 return 0; 78 } 79 /* 80 2 2 2 4 81 1 2 1 82 1 1 4 83 2 2 3 84 2 1 2 85 86 2 2 1 4 87 1 2 1 88 1 1 4 89 2 2 3 90 2 1 2 91 92 2 2 2 0 93 */