题意：构造一个有n个顶点，每个点度不超过k，然后给出每一个点到达一个定点的最短距离d数组，然后构造出这样的一个图；
思路：排序之后，有两个距离为0的或者没有直接输出-1，然后用两个游动下表，后面的与前面的度都小于k且它们的距离相差1，就建1条边。然后dfs输出就可以。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#define maxn 100010
using namespace std; int n,k;
int d[maxn];
int du[maxn];
struct node
{
int x,id;
bool operator <(const node &a)const
{
return x<a.x;
}
} p[maxn];
vector<int>g[maxn]; void dfs(int x)
{
for(int i=; i<(int)g[x].size(); i++)
{
printf("%d %d\n",x,g[x][i]);
dfs(g[x][i]);
}
} int main()
{
scanf("%d%d",&n,&k);
for(int i=; i<=n; i++)
{
scanf("%d",&d[i]);
p[i].x=d[i];
p[i].id=i;
}
sort(p+,p+n+);
if(p[].x==&&p[].x==||p[].x!=)
{
printf("-1\n");
return ;
}
int l=,r=;
int cnt=;
bool flag=false;
while(r<=n)
{
if(p[r].x==p[l].x)
{
printf("-1\n");
return ;
}
if(p[r].x-p[l].x==&&du[p[l].id]<k&&du[p[r].id]<k)
{
g[p[l].id].push_back(p[r].id);
cnt++;
du[p[l].id]++;
du[p[r].id]++;
r++;
}
else if(p[r].x-p[l].x>||du[p[l].id]>=k)
{
l++;
if(l==r)
{
flag=true;
break;
}
}
else if(du[p[r].id]>=k)
{
r++;
}
else
{
r++;
}
}
if(flag)
{
printf("-1\n");
return ;
}
printf("%d\n",cnt);
dfs(p[].id);
return ;
}