TOJ 4168 I-The brute force problem（数论）

<center> 4168. I-The brute force problem

Time Limit: 1.0 Seconds Memory Limit:65536K
Total Runs: 253 Accepted Runs:76 </center>

Xiao Ming is very interesting for array. He given a sorted positive integer array and an integer n.
We need add elements to the array such that the sum of subset of array cover the range [1, n]. You must return the minimum number of add elements.
Xiao Ming worry about you can't understand this problem. Now, he gives you an example:
There is an array [1, 3], n = 6, the answer is 1. Because we only need to add 2 into array. After add operator, the array is [1,2,3]. The subsets are: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].

Input

The input consists of multiple test cases. The first line contains an integer [Math Processing Error], indicating the number of test cases.
Each case contains two integers [Math Processing Error],

Output

Return the minimum number of add elements.

Sample Input

1
3 20
1 5 10

Sample Output

大致思路：

　　一开始想到二进制位上去了，觉得每个数的二进制位都有个贡献之类的，结果还是too naive啊，跟正解差的太多。

　　首先对子集A的元素排个序，然后假设当前子集中最大的数为a[i-1]，能够覆盖的范围是1~mx，那么如果a[i]>mx+1的话，必须要插入mx+1这个数才能使覆盖的范围仍旧连续，而插入mx+1，会使得覆盖的范围变成2*mx+1，此时再比较a[i]与当前的mx的大小，直到a[i]<=mx+1时加入a[i]会使得覆盖的范围变成mx+a[i]，一直这么考虑下去就ok。

复杂度分析：

　　首先对于数m来说，最多只需要log2(m)个数就可以满足题意了，那么插入的复杂度应该就是O(n+logm)，之前还需要排序，就是O(nlogn)，总的的复杂度即O(nlogn)了。

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const double eps=1e-7;
ll arr[100005];
int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        ll now=1;
        int m;
        ll n;
        scanf("%d%lld",&m,&n);
        for(i=0;i<m;i++)scanf("%lld",&arr[i]);
        ll zsm=0;
        int cnt=0;
        for(i=0;i<m;i++)
        {
            while(arr[i]>zsm+1)
            {
                zsm+=(zsm+1);
                cnt++;
            }
            zsm+=arr[i];
            if(zsm>=n)break;
        }
//        cout<<zsm<<" "<<cnt<<endl;  
        while(zsm<n)
        {
            zsm+=(zsm+1);
            cnt++;
        }
//        cout<<zsm<<" "<<cnt<<endl;
        printf("%d\n",cnt);
    }
}