首页 > 其他 > 详细

CCF-回收站选址(100分)

时间:2020-08-05 00:18:26      阅读:117      评论:0      收藏:0      [点我收藏+]

正确做法:

  暴力枚举每一个点,再枚举该点上下左右四个点,若都存在则符合题目要求
  进一步的枚举斜的四个点,得出答案  

时间复杂度:o(n^3)

#include<iostream>
#include<vector>
using namespace std;
typedef pair<int ,int> PII;
int res[5];
int main(){
    vector<PII> q;
    int n;
    cin>>n;
    while(n--){
        int x,y;
        cin>>x>>y;
        q.push_back(make_pair(x,y));
    }
    for(int i=0;i<q.size();i++){
        int cnt=0;
        int x=q[i].first,y=q[i].second;
        for(int j=0,flag=0;j<q.size();j++){
            if (q[j].first==x&&q[j].second==y+1)flag++;
            if (q[j].first==x&&q[j].second==y-1)flag++;
            if (q[j].first==x+1&&q[j].second==y)flag++;
            if (q[j].first==x-1&&q[j].second==y)flag++;
            if (flag==4){//代表满足题目要求的上下左右都存在垃圾
                for(int k=0;k<q.size();k++){
                    if (q[k].first==x+1&&q[k].second==y+1)cnt++;
                    if (q[k].first==x-1&&q[k].second==y+1)cnt++;
                    if (q[k].first==x+1&&q[k].second==y-1)cnt++;
                    if (q[k].first==x-1&&q[k].second==y-1)cnt++;
                }
                res[cnt]++;
                break;
            }
        }
    }
    for(int i=0;i<5;i++)cout<<res[i]<<endl;
    return 0;
}

若开二维数组来维护图的关系则可以减少一重循环,时间复杂度为o(n^2),但后五个测试数据的点可能存在1e9附近的数,数组不能开那么大,故只能过一半的数据

CCF-回收站选址(100分)

原文:https://www.cnblogs.com/wyf-fighting/p/13436354.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!