NC214446. 排解忧伤
描述
猪猪参加小米赞助的icpc比赛之后惨遭打铁，为了排解忧伤，他开始观察嘉宾席。
嘉宾席是间隔为1，一字排开的n个座椅，从左至右标号为1到n。有m个嘉宾，每个嘉宾有一个心仪座位Ai，注意，不同嘉宾的心仪座位可能相同。嘉宾们会统一从一排座位的最左侧依次入场。一个嘉宾首先会走到他心仪的位子，如果此时他发现没有人坐，他就会立刻占据这个位子。如果已经有人坐了，该嘉宾会继续向右走，直到遇到一个空位子，立刻坐下。每个嘉宾的怒气值是他额外行走的距离，也就是最终的座位到心仪座位的距离。如果走到最后都没有找到位置，嘉宾会怒气爆棚。
显然，座位存在一个先到先得的关系，不是每个人都能坐到心仪的座位。现在，猪猪想思考什么样的入场顺序可以使嘉宾们怒气值之和最小，请你帮帮他。
输入描述
第一行两个正整数n，m
第二行m个用空格隔开的正整数，从左往右第i个正整数表示Ai0<m<=n<=100000,0<Ai<=n
输出描述
一行一个正整数表示最小怒气和
示例1
输入:
5 4 3 2 4 3
输出:
2
C 解法, 执行用时: 15ms, 内存消耗: 1604K, 提交时间: 2021-06-10 20:18:52
#include<stdio.h>
long long sum=0;
int main()
{
int n,m,j,k,l,i;
int a[100001];
int b[100001]={0};
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d",&a[i]);b[a[i]]++;
}
for(i=1,l=0;i<=n;i++){
sum+=l;
if(b[i]>1){
l+=b[i]-1;continue;}
else
if(b[i]==0&&l!=0)
l--;
}
if(l==0)
printf("%lld",sum);
else
printf("-1");
}
C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 1276K, 提交时间: 2021-02-28 15:35:53
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n,m,x;
long long ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d",&x);
a[x]++;
}
for(int i=1;i<=n;++i){
x=max(0,a[i]-1);
ans+=x;
a[i+1]+=x;
}
printf("%lld\n",a[n+1]?(-1):ans);
}