【题意】给定一个DAG上每个点和多少个点间接连接,然后要让我们自己搞一个图,满足这个条件。

【解题方法】贪心水题。将顶点按能到达的点数从小到大排序,排好序之后每个点只能往前面的点连边. 因而如果存在一个排在第i位的点,要求到达的点数大于i-1,则不可行;否则就可以按照上述方法构造出图. 复杂度O(N^2).注意,这哥地方数字开小会TLE,队友把数组改成2010的才能过,不然TLE。。。可能姿势问题。

【AC 代码】

#include<cstdio>
#include<algorithm>
using namespace std;
const int N =2100;
struct node
{
    int id,x;
}a[N];
node ans[N*N];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int isok(int n)
{
    for(int i=0;i<n;i++){
        int t=a[i].x;
        for(int j=0;j<i;j++){
            if(a[j].x==a[i].x) break;
            t--;
        }
        if(t>0) return 0;
    }
    return 1;
}
int main()
{
    int T,res=1,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i].x);
            a[i].id=i+1;
        }
        sort(a,a+n,cmp);
        if(!isok(n)) printf("Case #%d: No\n",res++);
        else{
            int num=0;
            for(int i=0;i<n;i++){
                int t=a[i].x;
                for(int j=0;j<i;j++){
                    if(a[j].x==a[i].x) break;
                    if(t<=0) break;
                    t--;
                    ans[num++]={a[i].id,a[j].id};
                }
            }
            if(num==0) printf("Case #%d: Yes\n",res++);
            else{
                printf("Case #%d: Yes\n%d\n",res++,num);
                for(int i=0;i<num;i++) printf("%d %d\n",ans[i].id,ans[i].x);
            }
        }
    }
    return 0;
}