NC24274. 出逃
描述
Farmer John已经厌烦了奶牛在清晨出逃，他觉得受够了：是时候采取强硬措施了。他在牛棚的墙上钉了一个计数器，追踪从上次出逃开始经过的天数。所以如果某一天早上发生了出逃事件，这一天的计数器就为0；如果最近的出逃是3天前，计数器读数就为3。Farmer John一丝不苟地记录了每一天计数器的读数。
年末到了，Farmer John准备做一些统计。他说，你们这些奶牛会付出代价的！然而意想不到的是，他的记录的一些条目竟然丢失了！
Farmer John确信他是在发生出逃的某一天开始记录的。请帮助他确定，在所有与残留记录条目一致的事件序列中，基于记录的时间，最少和最多可能发生的出逃次数。
输入描述
输入的第一行包含一个整数NN（1≤N≤100），表示从Farmer John开始对奶牛出逃计数器进行计数以来已经经过的天数。
第二行包含N个空格分隔的整数。第i个整数是−1，表示第ii天的记录丢失了，或者是一个非负整数ai（不超过100），表示在第i天计数器的数字是ai。
输出描述
如果没有事件序列与Farmer John的残留记录以及他所确定的奶牛在第1天清晨出逃这一事实相一致，输出一个整数−1。否则，输出两个空格分隔的整数m和M，其中m为所有事件序列中出逃的最少次数，M为最多次数。
示例1
输入:
4 -1 -1 -1 1
输出:
2 3
说明:
在这个样例中，我们可以推断第3天必然有出逃发生。我们已经知道在第1天也发生了出逃，所以最后不确定的只有第2天是否发生了出逃。因此，总共发生了2至3次出逃。C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 400K, 提交时间: 2019-06-29 20:50:34
#include<bits/stdc++.h>
using namespace std;const int M=101;
int a[M],f[M],g[M],mx;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(a[1]!=0&&a[1]!=-1){printf("-1\n");return 0;}
for(int i=1;i<=n;i++)if(a[i]!=-1){
if(mx>i-a[i]){printf("-1\n");return 0;}
mx=i-a[i];
}
a[1]=0;for(int i=1;i<=n;i++)
if(a[i]==-1)f[i]=f[i-1],g[i]=g[i-1]+1;
else f[i]=f[i-a[i]-1]+1,g[i]=g[i-a[i]-1]+1;
printf("%d %d\n",f[n],g[n]);
}
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2019-06-29 10:17:07
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],ans,res;
int main(){
int n,f=1;
scanf("%d%d",&n,&a[1]);
if(a[1]>=1)f=0;
else a[1]=0;
for(int i=2;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>=1){
for(int j=i-a[i],t=0;j<i;j++,t++){
if(a[j]==-1)a[j]=t;
if(a[j]!=t)f=0;
}
}
}
if(!f)puts("-1");
else{
for(int i=1;i<=n;i++)
if(a[i]==0)ans++;
else if(a[i]==-1)res++;
printf("%d %d\n",ans,ans+res);
}
return 0;
}