[ACM_ZJUT_1063]Lily's Puzzle
杰拉斯 | 时间:2012-04-28, Sat | 8,691 views编程算法
Lily's puzzle
Time Limit:1000MS Memory Limit:32768K
Description
最近lily的好朋友Kingly在农场里干活,农场里种了很多树,Kingly的任务就是:给定树的位置,然后到农场里清点树的棵数,由于他比较死板,只会一棵棵去数,所以他的工资比别人少。而lily就提醒他用计算机,因为这是计算速度最快的东东!同时lily又想到了一个问题:如果给定一个区域的尺寸,怎么样才能数出这个范围内的树最多?
举个例子,在下图中,农场是一个宽为10长为8的矩形。
每个(*) 代表一棵树。 如果给定区域的一边为4另一边为3的,那么显然是左上方的小矩形区域中的树最多,是5棵。 你的任务就是解决上述的问题!
Input
输入有多组测试数据,每组数据的格式如下: N W H x1 y1 x2 y2 ... xN yN S T N是树的总数(0<N<=500) , W 和 H 分别是农场的宽和长。 你可以假设W 和 H 是正整数他们的值不大于100。 每个i (1 <= i <= N), xi 和 yi 是第i棵树的坐标 。 你可以假设 1 <= xi <= W 和 1 <= yi <= H, 没有两棵树的位置是相同的,但是你不能假设树是以某种顺序排列好的。最后 S 和 T 是给定区域的两条边(均为整数),你可以假设 1 <= S ,T <= min(W,H)。 唯一的一个0代表输入结束。
Output
对于每组数据,请输出一个整数,代表给定区域中最多几棵树!
Sample Input
16 10 8 2 2 2 5 2 7 3 3 3 8 4 2 4 5 4 8 6 4 6 7 7 5 7 8 8 1 8 4 9 6 10 3 4 3 8 6 4 1 2 2 1 2 4 3 4 4 2 5 3 6 1 6 2 3 2 0
Sample Output
5 3
Source
穷举(TLE):
#include<stdio.h> #include<memory> int a[101][101]; int b[101][101]; int Solve(int w, int h, int s, int t){ int row, col, i, j, k, max; for(i = 1; i <= t; ++i){ for(j = 1; j <= s; ++j){ b[1][1] += a[i][j]; } } max = b[1][1]; for(i = 2; i <= h - t + 1; ++i){ b[i][1] = b[i - 1][1]; for(j = 1; j <= s; ++j){ b[i][1] += a[i - 1 + t][j] - a[i - 1][j]; } if(max < b[i][1]) max = b[i][1]; } for(k = 2; k <= w - s + 1; ++k){ b[1][k] = b[1][k - 1]; for(i = 1; i <= t; ++i){ b[1][k] += a[i][k - 1 + s] - a[i][k - 1]; } if(max < b[1][k]) max = b[1][k]; for(i = 2; i <= h - t + 1; ++i){ b[i][k] = b[i - 1][k]; for(j = k; j <= k + s - 1; ++j){ b[i][k] += a[i - 1 + t][j] - a[i - 1][j]; } if(max < b[i][k]) max = b[i][k]; } } return max; } int main(){ int trees, w, h, s, t, i, j; while(scanf("%d", &trees) && trees){ memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%d%d", &w, &h); while(trees--){ scanf("%d%d", &j, &i); a[i][j] = 1; } scanf("%d%d", &s, &t); int max = Solve(w, h, s, t); if(s != t){ memset(b, 0, sizeof(b)); int tmp = Solve(w, h, t, s); if(tmp > max) max = tmp; } printf("%d\n", max); } return 0; }
超哥 13:51:13
算法复杂度可以降到O(N* min(S,T)) + O(WH)你的算法是从格子计数,可以从树的角度出发,
如先考虑一个 O(N*S*T) + O(WH)复杂度的算法即b[i][j]是左上角坐标为(i,j)格子所对应 长度为(S*T)矩阵内的树的个数,
先从树的个数做循环(输入中,把树的坐标全部压如vector)每个数最多属于 S*T个矩阵,如果他属于b[i][j],则 b[i][j]++;
最后用一个 O(WH)的循环把b[i][j]的最大值找出来。
类似这个思路,可以推出一个更小复杂度的 O(N* min(S,T)) + O(WH)
可是又是一个TLE:
#include<stdio.h> #include<memory> #include<vector> using namespace std; int a[101][101]; struct T{ int row, col; T(int row, int col):row(row), col(col){} }; int Solve(vector<T> &v, int w, int h, int s, int t){ int i, j, max = 0; memset(a, 0, sizeof(a)); for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){ for(i = (*it).row; i > (*it).row - s && i > 0; --i){ for(j = (*it).col; j > (*it).col - t && j > 0; --j){ ++a[i][j]; if(a[i][j] > max) max = a[i][j]; } } } return max; } int main(){ int trees, w, h, s, t, i, j; while(scanf("%d", &trees) && trees){ vector<T> v; scanf("%d%d", &w, &h); while(trees--){ scanf("%d%d", &j, &i); v.push_back(T(j, i)); } scanf("%d%d", &s, &t); int max = Solve(v, w, h, s, t); if(s != t){ int tmp = Solve(v, w, h, t, s); if(tmp > max) max = tmp; } printf("%d\n", max); } return 0; }
很神奇地,把scanf改为cin就通过了(以上两种方法都可以AC,据说是某些编译器对于cin会有所优化):
#include<iostream> #include<memory> using namespace std; int a[101][101]; int b[101][101]; int Solve(int w, int h, int s, int t){ int row, col, i, j, k, max; for(i = 1; i <= t; ++i){ for(j = 1; j <= s; ++j){ b[1][1] += a[i][j]; } } max = b[1][1]; for(i = 2; i <= h - t + 1; ++i){ b[i][1] = b[i - 1][1]; for(j = 1; j <= s; ++j){ b[i][1] += a[i - 1 + t][j] - a[i - 1][j]; } if(max < b[i][1]) max = b[i][1]; } for(k = 2; k <= w - s + 1; ++k){ b[1][k] = b[1][k - 1]; for(i = 1; i <= t; ++i){ b[1][k] += a[i][k - 1 + s] - a[i][k - 1]; } if(max < b[1][k]) max = b[1][k]; for(i = 2; i <= h - t + 1; ++i){ b[i][k] = b[i - 1][k]; for(j = k; j <= k + s - 1; ++j){ b[i][k] += a[i - 1 + t][j] - a[i - 1][j]; } if(max < b[i][k]) max = b[i][k]; } } return max; } int main(){ int trees, w, h, s, t, i, j; while(cin >> trees && trees){ memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); cin >> w >> h; while(trees--){ cin >> j >> i; a[i][j] = 1; } cin >> s >> t; int max = Solve(w, h, s, t); if(s != t){ memset(b, 0, sizeof(b)); int tmp = Solve(w, h, t, s); if(tmp > max) max = tmp; } cout << max << endl; } return 0; }
#include<iostream> #include<memory> #include<vector> using namespace std; int a[101][101]; struct T{ int row, col; T(int row, int col):row(row), col(col){} }; int Solve(vector<T> &v, int w, int h, int s, int t){ int i, j, max = 0; memset(a, 0, sizeof(a)); for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){ for(i = (*it).row; i > (*it).row - s && i > 0; --i){ for(j = (*it).col; j > (*it).col - t && j > 0; --j){ ++a[i][j]; if(a[i][j] > max) max = a[i][j]; } } } return max; } int main(){ int trees, w, h, s, t, i, j; while(cin >> trees && trees){ vector<T> v; cin >> w >> h; while(trees--){ cin >> j >> i; v.push_back(T(j, i)); } cin >> s >> t; int max = Solve(v, w, h, s, t); if(s != t){ int tmp = Solve(v, w, h, t, s); if(tmp > max) max = tmp; } cout << max << endl; } return 0; }
志伟哥的代码,思路是遍历所有位置,每个位置从vector中找到范围内的树,每找到一个,树的数目加1,最终比较得出结果:
#include<memory> #include<iostream> #include<vector> using namespace std; struct T{ int row, col; T(int row, int col):row(row), col(col){} }; int Solve(int i,int j,int s,int t,vector<T> v) { int suma=0; int sumb=0; for(int k=0;k<v.size();k++) { if(v[k].row<i+t && v[k].row>=i && v[k].col<j+s && v[k].col>=j) suma++; if(v[k].row<i+s && v[k].row>=i && v[k].col<j+t && v[k].col>=j) sumb++; } if(suma>=sumb) return suma; else return sumb; } int main() { int trees, w, h, s, t, i, j; while(cin>>trees && trees) { vector<T> v; cin >> w >> h; while(trees--) { cin >> j >> i; v.push_back(T(j, i)); } cin >> s >> t; int maxtree=0,temptree=0; for(int i=0;i<=w;i++) { for(int j=0;j<=h;j++) { temptree=Solve(i,j,s,t,v); if(temptree>maxtree) maxtree=temptree; } } cout << maxtree << endl; } return 0; }
三种方法运行结果如下:
Method | Result | Time(MS) | Memory(K) | Length | Language |
---|---|---|---|---|---|
穷举 | Accepted | 31 | 212 | 1197 | G++ |
遍历树 | Accepted | 10 | 252 | 1114 | G++ |
遍历位置 | Accepted | 13 | 288 | 1611 | G++ |
可以看出遍历树更好一些,毕竟树的数量要远小于位置数量。
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »