題目：Twinkle Twinkle Little Star

?

題意：就是給n個點的坐標，然后在這個圖形中找出一個邊長最小的正方形，要求正方形的邊平行于坐標軸且覆蓋的點大于等于k個。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N = 200010; const int INF = 999999999;struct Point {int x,y;bool operator < (const Point &a) const{if(x!=a.x) return x < a.x;return y < a.y;} };Point p[N];int n,k,y[N];int judge(int len) {int pre = -INF;for(int i=0,j;i<n;i++){if(pre!=p[i].x){pre = p[i].x;int cnt = 0;for(j=i;j<n;j++){if(p[j].x>=pre&&p[j].x<=pre+len)y[cnt++] = p[j].y;else break;}sort(y,y+cnt);if(cnt<k) continue;int pre1 = -INF;for(int r=0;r+k-1<cnt;r++){if(pre1!=y[r]){pre1 = y[r];int up = upper_bound(y,y+cnt,pre1+len)-y-r;if(up>=k) return 1;}}}}return 0; }int main() {int t=1;while(~scanf("%d%d",&n,&k)){for(int i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);sort(p,p+n);int R = max(p[n-1].x-p[0].x,p[n-1].y-p[0].y);int L = 0;int ret = 0;while(L<=R){int mid = (L+R)>>1;if (judge(mid)){ret = mid;R = mid-1;}else L = mid+1;}printf("Case %d: %d\n",t++,ret);}return 0; }

?

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的NEFU 635(二分+枚举)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。