题目链接:https://ac.nowcoder.com/acm/contest/38105/J
大意是给出一堆数,求是否存在一个图,它的顶点的连接数量与序列相对应。
困难版本不考虑,,,
思路:优先队列从大数量边的点开始考虑,一个个进行满足,存在无法满足的no,直到最后yes
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') priority_queue<int> q; int n; cin>>n; int x; for(int i=1;i<=n;i++){ cin>>x; q.push(x); } while(!q.empty()){ int a = q.top(); q.pop(); vector<int> ve; while(a&&q.size()){ int b = q.top(); q.pop(); if(b){ a--; ve.push_back(b-1); } } if(a){ cout<<"NO"<<endl; return 0; } for(auto i:ve){ q.push(i); } } cout<<"YES"<<endl; }