企业官网建设流程全解析

P8297 [COCI 2012/2013 #2] LANCI

题目背景

本题分值按 COCI 原题设置，满分100100100。

题目描述

Mirko 在阁楼里发现了NNN个链。每个链由一些节组成，其中每个节最多有两个相邻节。每个节都可以打开或合上，因此可以将链分开或连成更长的链。

Mirko 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的节。

例如，假设 Mirko 只有333个链，每个链只有一个节，他可以打开其中一个，并且连上另外两个再合上。

给定链的数量以及每个链的长度，找到 Mirko 必须打开和关闭的最小节数，使它们全部在一个长链上。

输入格式

第一行一个整数N (2≤N≤5×105)N\ (2\le N\le 5\times 10^5)N(2≤N≤5×105)，表示链的数量。

第二行NNN个正整数Li (1≤Li≤106)L_i\ (1\le L_i\le 10^6)Li​(1≤Li​≤106)，表示第iii个链的长度。

输出格式

输出仅一行一个整数，表示最少要打开的节数。

输入输出样例 #1

输入 #1

2 3 3

输出 #1

1

输入输出样例 #2

输入 #2

3 1 1 1

输出 #2

1

输入输出样例 #3

输入 #3

5 4 3 5 7 9

输出 #3

3

C++实现

#include<bits/stdc++.h>usingnamespacestd;longlongread(){longlongx=0,sgn=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}returnx*sgn;}longlongn,ans,a[500010],sum;intmain(){n=read();for(inti=1;i<=n;i++)a[i]=read();sort(a+1,a+n+1);ans=n-1;//先全部首尾相连在一起for(inti=1;i<=n;i++){sum+=a[i];if(sum==n-i-1){//恰好相等，样例 3 所示情况ans=min(ans,sum);break;}if(sum>n-i-1){//不用全拆，需求粘合剂个数 +1ans=min(ans,n-i);break;}}printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容