题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4721
题意：n 个蚯蚓，m 秒内每秒长♂大一些，每秒找到最♂大的那个按照某比例切成两段，输出每次最♂大的那个和最后的所有大小
构造三个队列，没被切的，切后较长段，较短段。显然三个队列都是单调递减的... 因为本来就小的不会长得比本来就比它大的大...
那么就可以了... 然而此题坑点奇多...
首先必须手写队列，不然 T 飞。
其次不能狂开 long long，否则 T 飞。
然后要读入优化 (大概 ，不然 T 飞
最后注意输出格式，否则 PE....
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define M 7000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,q,u,v,t; int hda=1,hdb=1,hdc=1; int tla,tlb,tlc; int a[N],b[M],c[M]; bool cmp(int x,int y) {return x>y;} ll get_top(int x) { ll x1,x2,x3,mx; x1=x2=x3=-1; if(hda<=tla) x1=a[hda]+(x-1)*q; if(hdb<=tlb) x2=b[hdb]+(x-1)*q; if(hdc<=tlc) x3=c[hdc]+(x-1)*q; mx=max(x1,max(x2,x3)); if(mx==x1) {hda++;return x1;} if(mx==x2) {hdb++;return x2;} else {hdc++;return x3;} } int main() { n=read(),m=read(),q=read(),u=read(),v=read(),t=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1,cmp);tla=n; for(int i=1;i<=m;i++) { ll tp=get_top(i); if(i%t==0) { if(i!=t) printf(" "); printf("%lld",tp); } ll tp1,tp2; tp1=tp*u/v,tp2=min(tp1,tp-tp1),tp1=tp-tp2; b[++tlb]=tp1-i*q; c[++tlc]=tp2-i*q; } puts(""); for (int i=1;i<=n+m;i++) { ll tp=get_top(m+1); if(i%t==0) { if(i!=t) printf(" "); printf("%lld",tp); } } } |
Comments | NOTHING