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
ZJUT1063
窮舉(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++ |
可以看出遍歷樹更好一些,畢竟樹的數量要遠小于位置數量。
=======================簽 名 檔=======================
原文地址(我的博客): http://www.clanfei.com/2012/04/790.html
歡迎訪問交流,至于我為什么要多弄一個博客,因為我熱愛前端,熱愛網頁,我更希望有一個更加自由、真正屬于我自己的小站,或許并不是那么有名氣,但至少能夠讓我為了它而加倍努力。。
=======================簽 名 檔=======================
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
