hdu-5813 Elegant Construction(贪心)
题目链接:
Elegant Construction
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
A city with N towns (numbered 1 through N) is under construction. You, the architect, are being responsible for designing how these towns are connected by one-way roads. Each road connects two towns, and passengers can travel through in one direction.
For business purpose, the connectivity between towns has some requirements. You are given N non-negative integers a1 .. aN. For 1 <= i <= N, passenger start from town i, should be able to reach exactly ai towns (directly or indirectly, not include i itself). To prevent confusion on the trip, every road should be different, and cycles (one can travel through several roads and back to the starting point) should not exist.
Your task is constructing such a city. Now it's your showtime!
If Y is "Yes", output an integer M in a line, indicating the number of roads. Then M lines follow, each line contains two integers u and v (1 <= u, v <= N), separated with one single space, indicating a road direct from town u to town v. If there are multiple possible solutions, print any of them.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e18;
const int N=1e5+10;
const int maxn=5e3+4;
const double eps=1e-12; struct node
{
int a,id;
}po[N];
int cmp(node x,node y)
{
if(x.a==y.a)return x.id<y.id;
return x.a<y.a;
}
int main()
{
int t,Case=0,n;
read(t);
while(t--)
{
printf("Case #%d: ",++Case);
read(n);
int sum=0;
For(i,1,n)
{
read(po[i].a);
sum+=po[i].a;
po[i].id=i;
}
int flag=0;
sort(po+1,po+n+1,cmp);
For(i,1,n)
{
if(po[i].a>=i)
{
flag=1;
break;
}
}
if(flag)printf("No\n");
else
{
printf("Yes\n");
printf("%d\n",sum);
int num=0;
For(i,1,n)
{
for(int j=1;j<=po[i].a;j++)
{
printf("%d %d\n",po[i].id,po[j].id);
}
}
}
}
return 0;
}
最新文章
- 安卓android sharepreference数据存储,保存输入框里面的数据
- 17.Java 反射机制
- js 和 jq 控制 checkbox
- error C2065: “IDD_DIALOG1” : 未声明的标识符
- haskell rust相关文章
- java运用Comparator为对象排序
- JodaTime用法简介
- javaWeb中的/路径问题
- Sublime Text使用心得(一)
- java学习之url
- hadoop yarn 易理解
- kvm虚拟机中鼠标不同步的问题解决方法
- jenkins+svn+python+appium启动+mail+html报告
- 3ds max学习笔记(十二)-- (弯曲:实例旋转楼梯)
- 201904Online Human Action Recognition Based on Incremental Learning of Weighted Covariance Descriptors
- mysql单机多实例
- form表单中的encType属性
- 判断easyUI tree 节点复选框是否被选中的方法。将选中的节点高亮显示的方法
- html在线编辑器汇总
- long()