CCF 201912-2垃圾站选址

我不是女神ヾ 2023-07-13 03:21 3阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

#include<iostream>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    typedef pair<int, int> P;
    int score[6];
    vector<P> v;
    bool cmp(pair<int,int>a,pair<int,int>b){ 
        if(a.first!=b.first)return a.first<b.first;
        else return a.second<b.second;
    }
    //按照第一元素从小到大排
    //第一元素相同按照第二元素从小到大排
    int getScore(int pos) { 
        int scoreR = 0, scoreL = 0;
        int x = v[pos].first, y = v[pos].second;
        //保证前后左右都有垃圾
        bool up = false, down = false, left = false, right = false;
        //分左右
        //左
        for (int i = pos; i >= 0; i--) { 
            int tempx = v[i].first, tempy = v[i].second;
            if (tempx < x - 1)
                break;
            if (tempx == x - 1 && tempy == y)//左
                left = true;
            if (tempx == x - 1 && tempy == y + 1)//左上
                scoreL++;
            if (tempx == x - 1 && tempy == y - 1)//左下
                scoreL++;
            if (tempx == x && tempy == y - 1)//下
                up = true;
        }
        //右
        for (int i = pos; i < v.size(); i++) { 
            int tempx = v[i].first, tempy = v[i].second;
            if (tempx > x + 1)
                break;
            if (tempx == x + 1 && tempy == y)//右
                right = true;
            if (tempx == x + 1 && tempy == y + 1)//右上
                scoreR++;
            if (tempx == x + 1 && tempy == y - 1)//右下
                scoreR++;
            if (tempx == x && tempy == y + 1)//上
                down = true;
        }
    
    
    
        if (up && down && left && right)
            return scoreL + scoreR;
        else return -1;
    
    
    }
    
    int main() { 
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { 
            P tempP;
            scanf("%d%d", &tempP.first, &tempP.second);
            v.push_back(tempP);
        }
        //从小到大排序
        sort(v.begin(), v.end(),cmp);
        for (int i = 0; i < v.size(); i++) { 
    
            int type = getScore(i);
            if (type > -1)
                score[type]++;
        }
        for (int i = 0; i < 5; i++) { 
            printf("%d\n", score[i]);
        }
        return 0;
    }
    /* 7 1 2 2 1 0 0 1 1 1 0 2 0 0 1 11 9 10 10 10 11 10 12 10 13 10 11 9 11 8 12 9 10 9 10 11 12 11 */

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309214454955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309214232726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70