Problem

洛谷P2827 题目地址

Solution

直接用优先队列模拟可以得到不少的分数，时间复杂度 $O(m \log m),m<=7*10^6$ ，但是并不能通过此题，我们要考虑挖掘一些性质优化时间复杂度。

假设现在有两条蚯蚓，长度分别记为 $x_1,x_2$，且满足 $x_1>=x_2$。

令 $l_1$ 表示 $x1$ 切掉后 $\lfloor px_1 \rfloor$ 这部分（left左边），$r_1$ 表示切掉后 $x_1 - \lfloor px_1 \rfloor$ 这部分（right右边），$l_2,r_2$ 同理。

当然随着时间的推移，$l_1,r_1$ 也要加上 $q$。根据题目意思，如果我们先切 $x_1$，$x_2$ 也会加上 $q$，此时 $l_2,r_2$ 会有所变化。

准确的说，假设 $x_1,x_2$ 恰好是根据题意依次要切的两条蚯蚓的长度，那么：

$l_1=\lfloor px_1 \rfloor + q,r_1=x_1 - \lfloor px_1 \rfloor + q,$

$l_2=\lfloor p(x_2+q) \rfloor,r_2=x_2+q-\lfloor p(x_2+q) \rfloor.$

那么我们猜想 $l_1>=l_2$，$r_1>=r_2$。下面通过推式子来证明。

• 证明 $l_1>=l_2$

$$\because l_1=\lfloor px_1 \rfloor + q=\lfloor px_1+q \rfloor,$$

$$l_2=\lfloor p(x_2+q) \rfloor = \lfloor px_2 + pq \rfloor,$$

$$x_1>=x_2,0<p<1,$$

$$\therefore px_2<=px_1,pq<q $$

$$\therefore l_1>l_2$$

（我们还多推导出 $l_1 ≠ l_2$，qwq）

• 证明 $r_1>=r_2$

$$r_1>=r_2 \leftrightarrow r_1-r_2>=0$$

$$r_1-r_2=x_1-\lfloor px_1 \rfloor + q - (x_2+q-\lfloor p(x_2+q) \rfloor)$$

$$=x_1-\lfloor px_1 \rfloor - x_2 + \lfloor p(x_2+q) \rfloor + q - q$$

$$=\lfloor x_1-px_1 \rfloor + \lfloor px_2+pq-x_2 \rfloor$$

$$=\lfloor (1-p)x_1 \rfloor + \lfloor (p-1)x_2 + pq \rfloor$$

推到这里不会了这么办？（因为取整的事，怎么提出来啊）我们假设可以将取整符号内的东西拆开来（但愿宇宙原谅这五公斤） 那么就有：

$$=\lfloor (1-p)x_1 \rfloor - \lfloor (1-p)x_2 \rfloor + \lfloor pq \rfloor$$

$$\therefore r_1 >= r_2.$$

证明了这个神奇的性质，那么假设我们依次要取出的数是 $x_1,x_2,x_3…x_m$，那么就会有 $x_1>=x_2>=x_3>=…>=x_m$，因此利用上面这个性质，就会有 $l_1>=l_2>=…>=l_m,r_1>=r_2>=…>=r_m$。到这里，我们发现了题目中隐含的单调性，因此我们可以这样来设计程序：开三个队列，分别存 $x,l,r$。 将原数列 $a_n$ 排序后加入第一个队列。每次从三个队列中选一个最大的，得到的 $l,r$ 直接加入 $L$ 队列和 $R$ 队列尾部（因为我们证明了可以这样），而且最大的一定是队头，这样我们就实现了 $O(1)$ 查询最大值。因此总时间复杂度 $O(n \log n + m)$。

Code

Talk is cheap.Show me the code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f
#define N 7000007
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<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int n,m,q,u,v,t,ofst;   //offsetÆ«ÒÆÁ¿ 
int h=1,h1=1,h2=1,t1,t2;    //t1£¬t2²ÅÊÇÊý×é´óС£¬h1£¬h2ÊÇ¿ÉÓÃ×î´óÖµ 
int s[N],c1[N],c2[N];   //Ô­Êý×飬cut1£¬cut2
priority_queue<int> pq;
bool cmp(int a,int b) {
    return a > b;
}
int main()
{
    n = read(), m = read(), q = read(), u = read() ,v = read() ,t = read();
    double p = (double)u / (double)v;
    for(int i=1;i<=n;++i)
        s[i] = read();
    sort(s+1, s+1+n, cmp);
    for(int i=1;i<=m;++i) {
        int tp,a1,a2;
        if(h > n) c1[h1]>c2[h2] ? tp=c1[h1++] : tp=c2[h2++];
        else if(s[h]>=c1[h1] && s[h]>=c2[h2]) tp = s[h++];  //
        else if(c1[h1]>=s[h] && c1[h1]>=c2[h2]) tp = c1[h1++];
        else tp = c2[h2++];
        tp += ofst; a1 = floor(p*(double)tp); a2 = tp - a1;
        ofst += q; a1 -= ofst; a2 -= ofst;
        c1[++t1] = a1, c2[++t2] = a2;
        if(i % t==0) printf("%d ",tp);
    }
    putchar('\n');
    for(int i=h;i<=n;++i) pq.push(s[i]);
    for(int i=h1;i<=t1;++i) pq.push(c1[i]);
    for(int i=h2;i<=t2;++i) pq.push(c2[i]);
    int i = 0;
    while(!pq.empty()) {
        ++i; if(i%t==0) printf("%d ",pq.top()+ofst); pq.pop();
    }
    return 0;
}

Summary

通过这个题目，我学会了：

• 分析时间复杂度的瓶颈（查找最大值），向这方面优化，推导性质（单调性），最后回到算法，解决问题。