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个石子属于哪一堆。
样例输入
5 2 7 3 4 9 3 1 25 11
样例输出
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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash