本文主要是介绍uva 10720 Graph Construction(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题目其实挺简单的，uva上通过率却很低，今天晚上的第二道题，什么时候一个晚上我能做4道中等难度的题目
我就满意了。。。
思路：本来我是想着排序后然后遍历数组，将当前i的后面a[i]个值一次减一，然后继续遍历继续重复这样做，里面
包含着条件，如果有数变成负数就不成立，或者后面的点小于当前的度数也不成立，然后就TLE了，这个方法是错误
的，因为当序列为 4 4 3 3 2 2的时候最后一个2就会比前面变成1的数字大，需要重新排序的。。。我是稍微瞄
了一眼别人提交的代码才想起来的，每次处理最大数字都得重新排序。。然后继续处理。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>using namespace std;
int a[10005];
int cmp(const void *a,const void *b)
{return *(int *)b - *(int *)a;
}
int main()
{int n,i,j;while(cin >> n,n){for(i=1; i<=n; i++)cin >> a[i];int flag1 = 0;for(i=1; i<=n; i++){qsort(a+i,n-i+1,sizeof(a[0]),cmp);if(a[i] > n-i)//判断后面的点是否少于当前的度 {flag1 = 1;break;}for(j=1; j<=a[i]; j++){a[i+j]--; if(a[i+j] < 0)//判断是否有小于0的点 {flag1 = 1;break;}}if(flag1)break;}if(flag1)cout << "Not possible" << endl;elsecout << "Possible" << endl;} return 0;
}
这篇关于uva 10720 Graph Construction(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
