P2827——蚯蚓
wangyitong
2018-08-27 20:31:27
八十分：
直接拿个堆维护一下，以 当前len+当前到最后的时间*q
排序即可，然后每次取出来的时候减去后面即可，因为这样可以保证你每次取出来的都是加过q的，而一直到末尾的原因是他们每一段时候加的都是一样的。而不能记一个时间，然后每次取出来的时候加，因为你有可能取出来的那个不是最大的。但如果我们每次加的话就会挂，所以先加到末尾，最后再减就不会有问题。
但是优先队列多个log啊，然后就疯狂乱t；
不加硬核优化只有75(逃
```cpp
// luogu-judger-enable-o2
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define int long long
#define max maxx
#define min minn
using namespace std;
const int N=1e6+10;
template <class T> void in(T &x) {
x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if (f) x = -x;
}
inline int maxx(int x,int y) {
return x>y?x:y;
}
inline int minn(int x,int y) {
return x<y?x:y;
}
inline int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
int m,n,q,u,v,t,lennow,ans[10*N],cnt;
struct node {
int len;
int t;
bool operator < (const node& b)const {
return len<b.len;
}
} ew[8*N],t1,t2,x;
priority_queue<node> pq;
signed main() {
in(n),in(m),in(q),in(u),in(v),in(t);
// printf("%lf\n",p);
for(ri i=1; i<=n; ++i)
in(ew[i].len),ew[i].t=m-0,ew[i].len+=ew[i].t*q,pq.push(ew[i]);
/*for(ri i=1;i<=n;++i)
cout<<pq.top().len<<endl,pq.pop();*/
for(ri i=1; i<=m; ++i) {
x=pq.top();
//puts(" ");
// printf("%d %d %d\n",i,x.len,x.t);
lennow=x.len;
lennow-=(m-i+1)*q;
//printf("%d \n",lennow);
if(i%t==0)
cout<<lennow<<" ";
pq.pop();
t1.len=lennow*u/v,t1.t=m-i;
t2.len=lennow-t1.len,t2.t=m-i;
t1.len+=t1.t*q;
t2.len+=t2.t*q;
//printf("%d %d\n",t1.len,t1.t);
// printf("%d %d\n",t2.len,t2.t);
pq.push(t1);
pq.push(t2);
}
puts(" ");
while(!pq.empty()) {
cnt++;
if(cnt%t==0)
printf("%lld ",pq.top().len);
pq.pop();
}
puts(" ");
return 0;
}
```
100分：
留坑，代码来源：[ jzzcjb](https://www.luogu.org/space/show?uid=57304)
```cpp
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define max maxx
#define min minn
using namespace std;
const int N=1e7+10;
template <class T> void in(T &x) {
x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if (f) x = -x;
}
inline int maxx(int x,int y) {
return x>y?x:y;
}
inline int minn(int x,int y) {
return x<y?x:y;
}
inline int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
bool cmp(int a,int b) {
return a>b;
}
int n,m,sum,S,u,v,T,q[N],q1[N],q2[N],h,h1,h2,t,t1,t2;
int find() {
return (q[h]>max(q1[h1],q2[h2])&&(h<=t))?q[h++]:((q1[h1]>q2[h2])?q1[h1++]:q2[h2++]);
}
int main() {
in(n),in(m),in(S),in(u),in(v),in(T);
double p=(double)u/v;
t1=t2=0;
t=n;
h=h1=h2=1;
for(ri i=1; i<=n; ++i) scanf("%d",&q[i]);
sort(q+1,q+n+1,cmp);
for(ri i=1; i<=m; ++i) {
int x=find()+sum;
sum+=S;
int a1=p*(double)x,a2=x-a1;
q1[++t1]=(a1-=sum),q2[++t2]=(a2-=sum);
if(i%T==0)printf("%d ",x);
}
puts("");
q1[t1+1]=q2[t2+1]=-0x3f3f3f3f;
for(ri i=1,x=find(); i<=n+m; ++i,x=find())
if(i%T==0)printf("%d ",x+sum);
return 0;
}
```