NOI2010 超级钢琴
2018-06-27 10:01:45来源:未知 阅读 ()
题目大意:
懒得写了。。。。。。。
题解:
要求前k小,显然贪心。
假定我们选取了一个左端点op那么右端点的选取范围就固定在[op+L-1,op+R-1],那么我们可以维护一个三元组,即i与其选取范围。但我们会在某个区间选取诸如次大值,次次大值,次次次。。。。。。次大值。那么我们之前的三元组就还需要一个新的元素,即选取位置t。当我们使用了这个四元组之后,区间就应该删掉t,换一种思路,就是从t这个位置裂解成两个区间,次大值一定在这两个区间一种,这样我们依靠一个堆,重复以上操作即可。而在最大值的区间选取,我们可以依靠一个ST表来实现
时间复杂度:$O(nlog_2(n)+klog_2^2(n))$
1 #include<cstdio> 2 #include<queue> 3 void read(int &x){ 4 x=0;bool k=0; 5 char ch=getchar(); 6 while(ch<'0'||ch>'9') k=ch=='-'?1:k, ch=getchar(); 7 while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); 8 x=x*(k==1?-1:1); 9 } 10 const int N=500500; 11 int n,k,L,R; 12 int a[N],sum[N]; 13 inline int min(int a,int b){return a<b?a:b;} 14 struct node{int op,l,r,t; 15 friend bool operator <(node x,node y){ 16 return sum[x.t]-sum[x.op-1]<sum[y.t]-sum[y.op-1]; 17 } 18 }; 19 long long ans; 20 int mx[20][N]; 21 int lg[N],pow[20]; 22 inline void ST(){ 23 lg[0]=-1;for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1; 24 pow[0]=1;for(int i=1;i<=19;i++) pow[i]=pow[i-1]<<1; 25 for(int i=1;i<=n;i++) mx[0][i]=i; 26 for(int i=1;pow[i]<=n;i++) 27 for(int j=1;j<=n-pow[i]+1;j++){ 28 int t=mx[i-1][j],t1=mx[i-1][j+pow[i-1]]; 29 mx[i][j]=sum[t]>sum[t1]?t:t1; 30 } 31 } 32 inline int query(int l,int r){ 33 int q=lg[r-l+1]; 34 int t1=mx[q][l],t2=mx[q][r-pow[q]+1]; 35 return sum[t1]>sum[t2]?t1:t2; 36 } 37 std::priority_queue<node> q; 38 inline void solve(){ 39 for(int i=1;i<=n-L+1;i++) { 40 int l=i+L-1,r=min(i+R-1,n); 41 int t=query(l,r); 42 q.push((node){i,l,r,t}); 43 } 44 for(int i=1;i<=k;i++){ 45 node now=q.top();q.pop(); 46 ans+=sum[now.t]-sum[now.op-1]; 47 if(now.t+1<=now.r) 48 q.push((node){now.op,now.t+1,now.r,query(now.t+1,now.r)}); 49 if(now.t-1>=now.l) 50 q.push((node){now.op,now.l,now.t-1,query(now.l,now.t-1)}); 51 } 52 } 53 int main(){ 54 freopen("piano.in","r",stdin); 55 freopen("piano.out","w",stdout); 56 read(n),read(k),read(L),read(R); 57 for(int i=1;i<=n;i++) read(a[i]); 58 for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; 59 ST(); 60 solve(); 61 printf("%lld",ans); 62 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P3205 [HNOI2010]合唱队 2019-08-26
- 超级实用的属性浏览器控件--QtTreePropertyBrowser 2019-08-16
- nowcoder941B 弹钢琴 2019-08-16
- 超级简单的跨平台高性能音视频播放框架QtAv编译指南 2019-08-16
- BZOJ1191: [HNOI2006]超级英雄Hero(二分图匹配) 2018-07-09
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