首页 > > 程序设计 > C/C++ >

2018.8.15 题解 2018暑假集训之石子问题

2018-08-17 09:37:12来源：博客园阅读 ()

先放个题面描述

题目描述

WHM摆了N堆石子，他有点累，不想合并这些石子，所以他问了ZYC一个非常简单的问题：从左往右数第k个石子在哪一堆里？现在ZYC把这个问题分享给大家一起开心开心。

输入

输入第一行是一个数N，表示石子堆数。

第二行N个用空格隔开的数ai，表示从左往右第i堆有多少个石子。

第三行是一个数M，表示有M次询问。

第四行M个用空格隔开的数qi，表示WHM希望知道第qi个石子属于哪一堆。

输出

输出共有M行，每一行表示第qi个石子属于哪一堆。

样例输入

样例输出

1
5
3

提示

对于100%的数据，1<=N<=10^6 1<= M <=10^5 1<=ai<=1000。

这个题最开始想的是开一个dp数组存每个石子在哪一堆里

结果发现10^6*1000会超256MB

划重点！！！

于是我们可以换一个方向思考存截止到每一组有几个石子（前缀和思想）

（还记得dp的经典例题分组背包是怎么存的吗）

所以对于每一个石子的编号我们只需要找到相邻的两组可以恰好涵盖这个编号（比如说45号，找到一组37和48，即为48那一组）

但是容易发现这样搜会TLE 所以可以二分~

上代码吧

#include<stdio.h>
#include<ctype.h>
int n,m,a[1000005],q,qzh[1000005];
inline int read()//读入优化
{
    int x,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
    return x*f;
}
inline void write(int x)//输出优化
{
    int f=0;char ch[20];
    if(!x){putchar('0');return;}
    if(x<0){putchar('-');x=-x;}
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
}
int main()
{
   n=read();
   for(int i=1;i<=n;i++)
   {
       a[i]=read();
       qzh[i]=qzh[i-1]+a[i];//前缀和
   }
   m=read();
   for(int i=1;i<=m;i++)
   {
       q=read();
       int l=1,r=n;
       while(l<r)//二分的部分
       {
              int mid=(l+r)/2;
              if(qzh[mid]>=q)r=mid;
              if(qzh[mid]<q)l=mid+1;//注意这一部分！
               //我们考虑它的实际意义：
               //l表示左区间比q小的部分 r反之
               //所以l不可以选 r可以选
               //所以必须跳过l！跳过l！跳过l！
       }
       write(l);
   }
   return 0;
}