这是一题求完全平方数个数的题目。

关注到这题有多组数据，我们可以想到将所有完全平方数预处理，储存起来，询问时一一查询，此时该算法时间复杂度为，显然该时间复杂度过大，会导致超时。

可以发现，在区间中有且只有个完全平方数，亦可知区间中有且只有个完全平方数，那么我们就可以得到区间中有个完全平方数，此时时间复杂度为，满足我们的要求。当然，由于有可能为，而此时为负值，因此我们要特别判断这种情况，此时的区间内有个完全平方数。 

int get(int x)
{
    return x<0?0:sqrt(x)+1;
}

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        cout<<get(r)-get(l-1)<<endl;
    }
    //system("pause");
}

题目描述

贝西已经从公牛那里收到了N块巧克力(1<==N<=50,000)，但她不想吃得太快，所以她想计划下一个D(1<=D<=50,000)天的巧克力进食时间表，以便在这几天里最大限度地提高她的最低幸福感水平。

贝茜的幸福水平是一个整数，从0开始，晚上睡觉时减半(如果必要的话)。然而，当她吃巧克力I时，她的幸福水平会增加整数H_i(1<=H_i<=1,000,000)。如果她一天吃巧克力，那一天的快乐就被认为是她吃巧克力后的幸福水平。贝茜坚持按她收到的顺序吃巧克力。

如果存在多个最优解，请打印其中任何一个。

输入格式

第1行：两个分隔的整数：n和D

第2行.N+1：第I+1行包含一个整数：

输出格式

第1行：一个整数，贝茜在接下来的D天的最低幸福感

第2行..N+1：第I+1行包含一个整数，即贝茜吃巧克力的日子

题解

题目要求的是最小值最大，因此可以直接二分答案然后判定。

对于一个答案，如果开心值不够就不断的吃，需要注意的是所有剩下的都要在最后一天吃完。

先二分求出最不开心那天的最大开心值ans，再对ans重新check一遍以记录正确日期
原因：因为这个程序会不管三七二十一地把所有的日期记录下来，不管可行与否，所以只有当求出最优解ans后，check记录的日期才会是正解。

const int N=50010;
int a[N];
int day[N];
int n,m;

bool check(LL mid,bool ok)
{
    LL sum=0;
    int k=0;
    for(int i=1;i<=m;i++)
    {
        sum=sum>>1;
        while(k<n && sum < mid)
        {
            if(ok) day[k]=i;
            sum+=a[k++];
        }

        if(sum < mid) return false;
        //cout<<"---"<<i<<' '<<sum<<endl;
    }

    if(ok)
        for(int i=k;i<n;i++)
            day[i]=m;
    return true;
}

int main()
{
    cin>>n>>m;

    LL l=0,r=0;
    for(int i=0;i<n;i++) cin>>a[i],r+=a[i];

    while(l<r)
    {
        LL mid=l+r+1>>1;
        if(check(mid,0)) l=mid;
        else r=mid-1;
    }

    cout<<l<<endl;

    check(l,1);
    for(int i=0;i<n;i++)
        cout<<day[i]<<endl;

    //system("pause");
}

题意

歌曲由 个音符组成，第 个音符持续 拍。在时间 0 开始播放歌曲；
从时间 0 到时间 之前播放音符 1，从时间 到时间 之前播放音符 2，依此类推。
询问 个如下述形式的问题：在从时间 到时间 之前的间隔中，应该演奏哪个音符？

在时间 在 范围内时，演奏音符 1；
在时间 在 范围内时，演奏音符 2；
依此类推。

输入格式

第1行：两个空格分隔的整数：n和q

第2行.N+1：第I+1行包含单个整数：

第N+2.N+Q+1行：行N+I+1包含一个整数：

输出格式

第1行..Q：对于每个查询，打印一个整数，这是奶牛应该播放的音符的索引。

题解

解法一：使用upper_bound

const int N=50010;
int a[N];
int sum[N];
int n,m;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    while(m--)
    {
        int x;
        cin>>x;
        cout<<upper_bound(sum+1,sum+n+1,x)-sum<<endl;
    }
    //system("pause");
}

解法二：使用 map 记录时间节点 对应的音符，
就可以使用 map::lower_bound() 函数得出对应的演奏音符。

const int N=50010;
int a[N];
map<int,int> mp;
int n,m;

int main()
{
    cin>>n>>m;

    int sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        mp[sum-1]=i;
    }

    while(m--)
    {
        int x;
        cin>>x;
        auto it=mp.lower_bound(x);
        cout<<it->second<<endl;
    }
    //system("pause");
}

题目描述

牛牛有件材料和件材料，用件材料和件材料可以合成一件装备，用件材料和件材料也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。