mex
链接：HTTPS://AC.NOWCODER.COM/ACM/CONTEST/700/J
来源：牛客网
题目描述
recentLY MiniEYE’S ENGINEER M IS WORKING ON NEURAL NETWORK MODEL TRaiNING AND HE HAS FOUND THAT IF THE OUTPUT OF THE NETWORK IS S = (S1, S2, …, SN), THEN WE CAN USE MEX(S) TO PREDICT THE TOTAL TRAINING TIME OF THE NEURAL NETWORK. define MEX(S) AS:
HERE S’ ≤ S MEANS S’ IS A SUBsequence OF S, ∑S’ REPRESENTS THE SUM OF ALL ELEMENTS IN S’. Please NOTE THAT S’ CAN BE empty, AND IN THAT CASE ∑S’ IS 0.
M NEEDS YOUR HELP TO CALCULATE MEX(S).
输入描述:
THE FIRST LINE CONTAINS A SINGLE integer N(1 ≤ N ≤ 105).
THE SECOND LINE CONTAINS N NON-NEGATIVE INTEGERS SI(0 ≤ SI < 231).
输出描述:
print MEX(S) IN A SINGLE LINE.
示例1
输入
复制
3
1 2 5
输出
复制
4
说明
S’=(), ∑S’=0
S’=(1), ∑S’=1
S’=(2), ∑S’=2
S’=(1,2), ∑S’=3
S’=(5), ∑S’=5
THERE
IS NO WAY FOR ∑S’=4, HENCE 4 IS THE ANSWER.
正确题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int main()
{
int i,j,n,m,a[N]={0};
cin>>n;
for(i=1;i<n+1;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
if(a[1]!=1)
cout<<1;
else{
ll sum=0;
int f=0;
for(i=1;i<=n;i++){
sum+=a[i];
if(sum+1<a[i+1]){
f=1;
break;
}
}
cout<<sum+1;
}
}
错误题解：
#include<bits/stdc++.h>
using namespace std;
int main() {
long long i, j, n, m, a[100000], sum = 0;
cin >> n;
for(i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
int f = 0;
sum += 1;
sort(a, a + n);
if(a[0] = 1)
for(i = a[0]; i <= sum; i++) {
int temp = i, p;
for(j = 0; j < n; j++) {
if(a[j] >= i)
break;
}
p = j;
while(temp > 0 && p >= 0) {
if(temp < a[0])
break;
if(a[p] <= temp) {
temp -= a[p];
}
p–;
}
if(temp != 0) {
f = 1;
break;
}
}
else {
f = 1;
i = 1;
}
if(f == 1)
cout << i;
}
错误原因：
超时。
思考路线：
从K的取值出发全部遍历，导致每次都要从0开始进行，很费时间
真确解题思路：
抓住只要前面的和小于后面的和则会停止就可以了。
思维区别：
我仍然是遍历思维接近于暴力求解。
解题思维是找到规律用规律来写，就相当于写数学题目。。。。。
相关阅读
一、介绍linux系统有两个时钟：一个是由主板电池驱动的“Real Time Clock”也叫做RTC或者叫CMOS时钟，硬件时钟。当操作系统关机的时