2017 年广工大的程序设计决赛H题 --- tmk买礼物

真的是我遇到过的最坑的判题系统,要等两个小时才能等到结果.（这道题阻挡了我们去电科啊！！）题目在此

其实下来问了大佬,说是维护一个前缀和就可以了,当时不是太懂,后来仔细想想,就想通了,关键是当时比赛时我还想到了这一特点,就是没有的深入想下去,好气啊!!!

思路 ： 就是就是维护一个前缀和,因为有一个特点,就是从1连着的数字刚好可以构成从1到这些数字相加这么多数字,所以只要维护前缀和保持规律了就可以了,否则就直接跳出来就行了!!!

//就是前缀和,后面的数字如果大于前缀和+1 说明他和区间没有交集 前缀和+1这个数字达不到,就不连续了呗.!!!

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int main()
{
    int t;
    scanf("%d",&t);   //人笨啊!!!
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        ll ans=0;   //要用long long 才行,否则要WA.
        for(int i=0;i<n;i++){
            if(a[i]<=ans+1)   //维护前缀和保持为小于和+1就可以,否则就直接跳出来!!!
                ans+=a[i];
            else
                break;
            //printf("%d\n",ans);
        }
        printf("%lld\n",ans);
    }
}

记住这些水题的做法啊!!!