C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 612K, 提交时间: 2020-03-18 09:43:41

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
int n,amount=0;
vector<int> vec;
int link[105][105];
int out[105];
int visit[105];
void dfs(int x){
	int i,j;
	
	for(i=0;i<n;i++){
		if(link[x][i]==1){
			if(visit[i]==1) continue;
			visit[i]=1;
			amount++;//cout<<x<<" "<<i<<endl;
			dfs(i);
		}
	}
}
int main(){
	int i,j;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>j;
		vec.push_back(j);
	}
	sort(vec.begin(),vec.end());
	memset(link,0,sizeof(link));
	memset(out,0,sizeof(out));
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			link[j][i]=1;
		}
	}
	for(i=0;i<n;i++){
		out[i]=vec[i]-i;
	}
	for(i=0;i<n;i++){
		memset(visit,0,sizeof(visit));
		while(out[i]<0){
			int id=-1;
			for(j=0;j<i;j++){
				if(out[j]>0&&visit[j]==0&&(id==-1||out[j]>out[id])){
					id=j;
				}
			}
			visit[id]=1;
			out[i]++;
			out[id]--;
			link[i][id]=0;
			link[id][i]=1;
		}
	}
	/*for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cout<<link[i][j]<<" ";
		}
		cout<<endl;
	}*/
	for(i=0;i<n;i++){
		memset(visit,0,sizeof(visit));
		visit[i]=1;
		dfs(i);
	}
	cout<<amount+n<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 512K, 提交时间: 2019-11-11 20:04:55

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans;
int s[105][105];
struct point{
	int id,a,b;
}p[105];
bool comp(const point a1,const point a2){return a1.a<a2.a;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i].a);
		p[i].b=n-p[i].a-1;
		p[i].id=i;
	}
	for(int i=1;i<=n;i++){
		sort(p+i,p+n+1,comp);
		for(int j=n;j>=i+1;j--){
			if(!p[i].b) break;
			p[i].b--;p[j].a--;
			s[p[j].id][p[i].id]=1;
		}
		for(int j=i+1;j<=n;j++){
			if(!p[i].a) break;
			p[i].a--;p[j].b--;
			s[p[i].id][p[j].id]=1;
		}
		s[i][i]=1;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(s[i][k]&&s[k][j]) s[i][j]=1; 
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) ans+=s[i][j];
	}
	printf("%d\n",ans);
	return 0;
}