【每日一题】蚯蚓
蚯蚓
https://ac.nowcoder.com/acm/problem/16430
题意:
思路:
#include <cstdio> #include <queue> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n,m,q,u,v,t; double p; int a[N]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } struct que { int tag = 0; int a[7500005], l, r; que(){l = r = 1;} bool empty() {return l == r;} void push(int x) {a[r] = x - tag;++r;} void add() {tag += q;} int front() { return a[l] + tag;} int pop() {++l; return a[l-1] + tag;} }q1,q2,q3; //取出三个队列队头的最大值,并弹出 int getmx(){ int mx = -0x3f3f3f3f; int flag = 0; if(!q1.empty() && mx < q1.front()) {mx = q1.front();flag = 1;} if(!q2.empty() && mx < q2.front()) {mx = q2.front();flag = 2;} if(!q3.empty() && mx < q3.front()) {mx = q3.front();flag = 3;} switch(flag){ case 1 : q1.pop();break; case 2 : q2.pop();break; default : q3.pop(); } return mx; } void cut(int x) { q1.add(),q2.add(),q3.add(); q2.push(int(p*x)); q3.push(x - int(p*x)); } void solve(){ for(int i = 1;i <= m;i++){ int x = getmx(); if(i%t == 0) printf("%d ",x); cut(x); } puts(""); } int main(){ n = read(),m = read(),q = read(),u = read(),v = read(),t = read(); p = u * 1.0 / v; for(int i = 1;i <= n;i++) a[i] = read(); sort(a + 1,a + 1 + n); for(int i = n;i >= 1;i--) q1.push(a[i]); solve(); for(int i = 1;i <= n + m;i++){ int x = getmx(); if(i%t == 0) printf("%d ",x); } return 0; }
每日一题 文章被收录于专栏
每题一题题目