201912-2回收站选址
题目
题目链接:回收站选址
以下是题目截图:
思路
倦了,看代码。题目挺简单的,按要求做就行。
思路很简单,就是按住一个点不动,一个一个点地去试,看它满不满足垃圾站点的要求,然后再看它有多少分这样子。时间不会卡你的,看数据范围就知道了。
代码(附带样例)
/* 回收站选址 */
#include
using namespace std;
const int N = 1e3 + 10;
pair node[N], location[N];
int n, k;
bool is_near(pair a, pair b) {
if ((a.second == b.second && abs(a.first - b.first) == 1) ||
(a.first == b.first && abs(a.second - b.second) == 1))
return true;
else
return false;
}
bool get_score(pair a, pair b) {
if (abs(a.first - b.first) == 1 && abs(a.second - b.second) == 1)
return true;
else
return false;
}
int score[5];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> node[i].first >> node[i].second;
}
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (is_near(node[i], node[j])) count++;
if (count == 4) {
location[k++] = node[i];
break;
}
}
}
for (int i = 0; i < k; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (get_score(location[i], node[j])) count++;//这里开始时大意了,j对应的数组写成了location
score[count]++;
}
for (int i = 0; i < 5; i++) {
cout << score[i] << endl;
}
return 0;
}
/* 样例1
7
1 2
2 1
0 0
1 1
1 0
2 0
0 1
*/
/* 样例2
2
0 0
-100000 10
*/
/*样例3
11
9 10
10 10
11 10
12 10
13 10
11 9
11 8
12 9
10 9
10 11
12 11
*/
写在最后
写的时候注意看数据范围,刚开始我还以为他会很大,然后卡我时间,然后也就没有想到常规写法,钻进了别的地方去。后面一看,数据范围1e3
,那两个循环也就是1e6
小于1秒,可以用常规想法呀!
想起宿舍里的那位大佬的话,拿到题,先有思路,然后再动手,实在没有思路也要把暴力的方法写出来。