$1-N$中丢失了其中$K$个数,求剩下的集合不能组成的最小的自然数
假设现在$1~sum$中的任意一个数我都能组成,考虑下一个数$x$,如果$ x \le sum+1$,那么$1 - sum+x$中的任意一个数我都能组成,我们令$sum = sum + x$ ,继续执行即可。如果$x > sum+1$,那么$sum+1$我就不能组成,所以最小的无法组成的数就是$sum+1$,基于这样的思想,我们可以将丢失的数排序,然后完成这个模拟。
这篇文章讲的也挺好:点我
因为N最大只有1e9,其实我们可以标记1-5e5中的每个数是否存在,因为这些数加起来已经超过1e9了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n , k , a[N];
ll ans;

ll cal ( int l , int r ) {
    if ( l > r ) return 0;
    return 1LL * ( r - l + 1 ) * ( l + r ) / 2;
}

int main () {
    int T;
    scanf ( "%d" , &T );
    while ( T -- ) {
        scanf ( "%d%d" , &n , &k );
        for ( int i = 1 ; i <= k ; ++ i ) scanf ( "%d" , &a[i] );
        if ( ! k ) {
            ans = cal ( 1 , n ) + 1;
            puts ( ( ans % 2 ) ? "Chef" : "Mom" );
            continue;
        }
        sort ( a + 1 , a + k + 1 );
        a[k + 1] = n + 1;
        ans = 0;
        ans = cal ( 1 , a[1] - 1 );
        for ( int i = 1 ; i <= k ; ++ i ) {
            if ( a[i] + 1 == a[i + 1] ) continue;
            if ( a[i] + 1 > ans + 1 ) break;
            else {
                ans += cal ( a[i] + 1 , a[i + 1] - 1 );
            }
        }
        ++ ans;
        puts ( ( ans % 2 ) ? "Chef" : "Mom" );
    }
    return 0;
}
Last modification:February 21st, 2020 at 12:20 pm
如果觉得我的文章对你有用,请随意赞赏