本题题面原本极有诱惑性,甚至一度出题人想开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; }
原文:https://www.cnblogs.com/fzyzjiajia/p/13137970.html