首页 > 其他 > 详细

fzyzoiP4947 分班题解

时间:2020-06-15 22:04:20      阅读:40      评论:0      收藏:0      [点我收藏+]

本题题面原本极有诱惑性,甚至一度出题人想开specialjudge,显然后来我良心发现了


3.0的题目是不难的,主要是考验一下对代码细节的控制

不要被题面诱惑了,首先由题面这个诡异的表达而又没有开specialjudge,容易判断这题是贪心算法。

接下来进行分析,可以得出若有一条路径,一定是按班级编号从小到大进行遍历(注意题面中对遍历顺序没有限制)

再想什么时候可以走出这一条路径,一定是满足该条件:

设该妹子原来计划去的班级编号为k,则的对于她的所有的朋友一定包括1-k-1的所有编号且一定不包括k。 

(该条件的正确性请读者自行思考)

 

------------------------------------------------------------------------------------

其他:一定要注意细节!一定要注意细节!一定要注意细节!

O(n*m)的算法是勉强可过的,但是注意开快读以及不要用memset浪费时间

 

     

下面是AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
vector<int> q[MAXN];
struct sisterz{
    int classs;
    int num;
}a[MAXN];
bool flag[MAXN];
int n,m;
int fastread(){
    int ans=0;
    char p=getchar();
    while(p<0||p>9)
    p=getchar();
    while(p>=0&&p<=9){
        ans=ans*10+(p-0);
        p=getchar();
    }
    return ans;
}
bool cmp(sisterz aa,sisterz bb){
    if(aa.classs<bb.classs)
    return true;
    else
    return false;
}
int main(){
    int ai,bi;
    n=fastread();
    m=fastread();
    for(int i=1;i<=m;i++){
        ai=fastread();
        bi=fastread();
        q[ai].push_back(bi);
        q[bi].push_back(ai);
    }
    for(int i=1;i<=n;i++){
        a[i].classs=fastread();
        a[i].num=i;
    }
    for(int i=1;i<=n;i++){
        for(size_t j=0;j<q[i].size();j++)
            flag[a[q[i][j]].classs]=1;
        for(int j=1;j<a[i].classs;j++)
            if(flag[j]==0){
                printf("No\n");
                return 0;
            }
        if(flag[a[i].classs]==1){
            printf("No\n");
            return 0;
        }
        for(size_t j=0;j<q[i].size();j++)
            flag[a[q[i][j]].classs]=0;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        printf("%d ",a[i].num);
    printf("\n");
    return 0;
}

 

 

fzyzoiP4947 分班题解

原文:https://www.cnblogs.com/fzyzjiajia/p/13137970.html

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