2016 一中培训 day 5 ksum
2018-06-17 23:42:42来源:未知 阅读 ()
又是一天的爆零!!!!!
原本第一题 很容易做 竟然优化过度
丢了答案
1693: ksum
- Time Limit
- 1000 ms
- Memory Limit
- 524288 KBytes
- Judge
- Standard Judge
- Solved
- 18
- Submit
- 41
Description
Peter喜欢玩数组。NOIP这天,他从Jason手里得到了大小为n的一个正整数 数组。
Peter求出了这个数组的所有子段和,并将这n(n+1)/2个数降序排序,他想 知道前k个数是什么。
Input Format
输入文件名为 ksum.in。
输入数据的第一行包含两个整数 n 和 k。
接下来一行包含 n 个正整数,代表数组。
Output Format
输出文件名为 ksum.out。
输出 k 个数,代表降序之后的前 k 个数,用空格隔开。
Sample Input
input1 3 4 1 3 4 input2 3 3 10 2 7
Sample Output
output1 8 7 4 4 output2 19 12 10
Hint
测试点编号 n ≤ k ≤
1 100 5000
2 500 100000
3 1000 80000
4 1000 100000
5 10000 50000
6 20000 80000
7 50000 80000
8 100000 80000
9 100000 100000
10 100000 100000
对于所有数据,满足 ai≤10 9 k≤n(n+1)/2,n≤100000,k≤100000
明显的堆维护 对于一段连续序列 它的一系列次小值 一定是这段序列的子集;
只要每次取出 堆顶 将堆顶序列分别由 (l+1,r)&&(l,r-1)的子序列塞入堆中
进行堆维护即可 注意过程可能出现重复顶点 用哈希表维护即可;
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<vector> #define maxn 100010 using namespace std; struct st { int l,r; long long sum; }mu[2*maxn]; typedef pair<int,int> pa; map <pa,bool>q1; int n,m,k,l,n1,i; int a[maxn]; void down(int x) { int fa=x,son; while(fa*2<=n1) { son=fa*2; if(mu[son+1].sum>mu[son].sum&&son+1<=n1)son++; if(mu[fa].sum>mu[son].sum)break; swap(mu[fa],mu[son]); fa=son; } } void up(int x) { int fa,son=x; while(son/2) { fa=son/2; if(mu[fa].sum>mu[son].sum)break; swap(mu[fa],mu[son]); son=fa; } } void push (st x) { n1++; q1[pa(x.l,x.r)]=1; mu[n1]=x; up(n1); } int main() { // freopen("ksum.in","r",stdin); // freopen("ksum.out","w",stdout); scanf("%d%d",&n,&k); for(i=1;i<=n;++i) { scanf("%d",&a[i]); mu[1].sum+=a[i]; } n1=1;mu[1].l=1;mu[1].r=n;q1[pa(mu[1].l,mu[1].r)]=1; for(i=1;i<=k;++i) { printf("%lld ",mu[1].sum); if(mu[1].l<mu[1].r) { st q; q=mu[1]; q.sum-=a[q.l]; q.l++; if(!q1[pa(q.l,q.r)]) push(q); q=mu[1]; q.sum-=a[q.r]; q.r--; if(!q1[pa(q.l,q.r)]) push(q); } mu[1]=mu[n1--]; down(1); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- [NOIP2016]天天爱跑步-题解 2019-10-08
- 正睿暑期培训day1考试 2019-08-29
- 正睿暑期培训day4考试 2019-08-16
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