2 条题解
-
0
非离散化版(50分)
#include <bits/stdc++.h> using namespace std; int n,c; int sum[5010][5010]; bool check(int L){ for (int x1=1;x1<=5000-L+1;x1++)for(int y1=1;y1<=5000-L+1;y1++) { int x2=x1+L-1,y2=y1+L-1; if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= c) return true; } return false; } int main() { scanf("%d%d",&c,&n); memset(sum,0,sizeof(sum)); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); sum[x][y]++; } for(int i=1;i<=5000;i++) for(int j=1;j<=5000;j++) sum[i][j]+=sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; int l = 1,r = 5000,ans = 0; while (l<=r) { int mid = (l + r) >> 1; if (check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); return 0; }离散化版
#include <bits/stdc++.h> using namespace std; const int N=1010; struct node{int x,y;}p[N]; vector<int> b; int n,c,sum[N][N]; bool check(int L) { for(int x1=1;x1<b.size();x1++)for(int y1=1;y1<b.size();y1++) { int x2=upper_bound(b.begin(),b.end(), b[x1]+L-1)-b.begin()-1; int y2=upper_bound(b.begin(),b.end(), b[y1]+L-1)-b.begin()-1; if(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= c) return true; } return false; } int main() { scanf("%d%d",&c,&n); b.push_back(0); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); p[i]={x,y}; b.push_back(x); b.push_back(y); } sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end()); for(int i=1;i<=n;i++) { int x= lower_bound( b.begin(), b.end(),p[i].x)-b.begin(); int y= lower_bound( b.begin(), b.end(),p[i].y)-b.begin(); sum[x][y]++; } for(int i=1;i<b.size();i++) for(int j=1;j<b.size();j++) sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int l=1,r=10000,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1, ans=mid; // 如果满足条件，尝试更小的值 else l=mid+1; } printf("%d\n",ans); return 0; }离散化版（进一步优化）
#include <bits/stdc++.h> using namespace std; const int N=1010; struct node{int x,y;}p[N]; vector<int> b; int n,c,sum[N][N]; bool check(int L) { for(int x1=0,x2=1;x2<b.size();x2++) { while( b[x2] - b[x1 + 1] + 1 > L)x1++; for(int y1=0,y2=1;y2<b.size();y2++) { while( b[y2] - b[y1 + 1] + 1 > L)y1++; if(sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= c) return true; } } return false; } int main() { scanf("%d%d",&c,&n); b.push_back(0); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); p[i]={x,y}; b.push_back(x); b.push_back(y); } sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end()); for(int i=1;i<=n;i++) { int x= lower_bound( b.begin(), b.end(),p[i].x)-b.begin(); int y= lower_bound( b.begin(), b.end(),p[i].y)-b.begin(); sum[x][y]++; } for(int i=1;i<b.size();i++) for(int j=1;j<b.size();j++) sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int l=1,r=10000; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",l); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:14:52
非离散化版(50分)：
#include <bits/stdc++.h> using namespace std; int n,c; int sum[5010][5010];
bool check(int L){ for (int x1=1;x1<=5000-L+1;x1++)for(int y1=1;y1<=5000-L+1;y1++) { int x2=x1+L-1,y2=y1+L-1; if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= c) return True; } return False; } int main() { scanf("%d%d",&c,&n); memset(sum,0,sizeof(sum)); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); sum[x][y]++; } for(int i=1;i<=5000;i++) for(int j=1;j<=5000;j++) sum[i][j]+=sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
int l = 1,r = 5000,ans = 0; while (l<=r) { int mid = (l + r) >> 1; if (check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); return 0;}</pre>
离散化版：#include <bits/stdc++.h> using namespace std; const int N=1010; struct node{int x,y;}p[N]; vector<int> b; int n,c,sum[N][N]; bool check(int L) { for(int x1=1;x1<b.size();x1++)for(int y1=1;y1<b.size();y1++) { int x2=upper_bound(b.begin(),b.end(), b[x1]+L-1)-b.begin()-1; int y2=upper_bound(b.begin(),b.end(), b[y1]+L-1)-b.begin()-1; if(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= c) return True; } return False; } int main() { scanf("%d%d",&c,&n); b.push_back(0); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); p[i]={x,y}; b.push_back(x); b.push_back(y); } sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end()); for(int i=1;i<=n;i++) { int x= lower_bound( b.begin(), b.end(),p[i].x)-b.begin(); int y= lower_bound( b.begin(), b.end(),p[i].y)-b.begin(); sum[x][y]++; } for(int i=1;i<b.size();i++) for(int j=1;j<b.size();j++) sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int l=1,r=10000,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1, ans=mid; // 如果满足条件，尝试更小的值 else l=mid+1; } printf("%d\n",ans); return 0; }
离散化版（进一步优化）：#include <bits/stdc++.h> using namespace std; const int N=1010; struct node{int x,y;}p[N]; vector<int> b; int n,c,sum[N][N];</p>bool check(int L) { for(int x1=0,x2=1;x2<b.size();x2++) { while( b[x2] - b[x1 + 1] + 1 > L)x1++; for(int y1=0,y2=1;y2<b.size();y2++) { while( b[y2] - b[y1 + 1] + 1 > L)y1++; if(sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= c) return True; } } return False; } int main() { scanf("%d%d",&c,&n); b.push_back(0); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); p[i]={x,y}; b.push_back(x); b.push_back(y); } sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end()); for(int i=1;i<=n;i++) { int x= lower_bound( b.begin(), b.end(),p[i].x)-b.begin(); int y= lower_bound( b.begin(), b.end(),p[i].y)-b.begin(); sum[x][y]++; } for(int i=1;i<b.size();i++) for(int j=1;j<b.size();j++) sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; int l=1,r=10000; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",l); return 0; }
- 1