首页 > 代码库 > 【uva 1312】Cricket Field（算法效率--技巧枚举）
【uva 1312】Cricket Field（算法效率--技巧枚举）
题意：一个 L*R 的网格里有 N 棵树，要求找一个最大空正方形并输出其左下角坐标和长。(1≤L,R≤10000, 0≤N≤100)
解法：枚举空正方形也就是枚举空矩阵，先要固定一个边，才好继续操作。（P.S.许多类型的题都是这样：先固定一个变量，再比较另外的变量。这种思想在贪心、DP等都常出现，一定要掌握！）所以这题就是先枚举一条边的范围（横坐标），再枚举排序后的点，根据当前枚举的点和之前纵坐标最大的点的纵坐标得到这条边的长度，再比较、更新答案。
P.S.我这题打了2个小时！??º·(? ?????????? )?º·? 一定要注意细节啊！还有......我的行列是与题目相反着存的。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 using namespace std; 7 8 const int N=110,D=10010; 9 int n,l,r,m;10 struct node{int x,y;}a[N];11 int b[N];12 13 int mmin(int x,int y) {return x<y?x:y;}14 int mmax(int x,int y) {return x>y?x:y;}15 bool cmp(node x,node y)16 {17 if (x.y!=y.y) return x.y<y.y;18 return x.x<y.x;19 }20 int main()21 {22 int T;23 scanf("%d",&T);24 while (T--)25 {26 scanf("%d%d%d",&n,&r,&l);27 m=1; b[1]=0;28 for (int i=1;i<=n;i++)29 {30 scanf("%d%d",&a[i].y,&a[i].x);//31 b[++m]=a[i].x;32 }33 b[++m]=l;//没有+1...34 sort(a+1,a+1+n,cmp);35 sort(b+1,b+1+m);36 int p=1;37 for (int i=2;i<=m;i++)38 if (b[i]!=b[i-1]) b[++p]=b[i];39 m=p;40 41 int tx=0,ty=0,ans=0;42 for (int i=1;i<=m;i++)43 for (int j=i+1;j<=m;j++)44 {45 int mxy=0,tmp;46 for (int k=1;k<=n;k++)47 {48 if (a[k].x<b[i]||a[k].x>b[j]) continue;//别轻易break49 tmp=mmin(b[j]-b[i],a[k].y-mxy);50 if (tmp>ans) {ans=tmp; tx=b[i]; ty=mxy;}51 if (a[k].x!=b[i] && a[k].x!=b[j]) mxy=a[k].y;52 }53 tmp=mmin(b[j]-b[i],r-mxy);//边界勿漏54 if (tmp>ans) {ans=tmp; tx=b[i]; ty=mxy;}55 }56 printf("%d %d %d\n",ty,tx,ans);57 if (T) printf("\n");58 }59 return 0;60 }
【uva 1312】Cricket Field（算法效率--技巧枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。