题解：P9225 「PEOI Rd1」寻宝（treasure）

· · 题解

集训听了贪心的做法，乃大惊，遂写题解记录。

就拿第二个样例举例：

3
1 2 100
1 2 1

第 1 台机器的开动时间序列是 1,2,3,4,5,...；第 2 台机器的开动时间序列是 2,4,6,8,10,...；第 3 台机器的开动时间序列是 100,101,102,103,104,...。

对于第 1 台机器，我们显然只会使用它偶数次。考虑将相邻两项合并，得到 3,7,11,...。显然现在这台机器每生产一次的价值翻倍，就等价于又来了一台第 2 台机器，既然这两台机器每生产一次的价值相同，我们可以将 3,7,11,... 与 2,4,6,8,10,... 合并，得到 2,3,4,6,7,8,... 新的序列，因为所有序列都是递增的，我们可以归并排序实现。

同理，对于新的序列，我们仍然只会使用它偶数次。相邻两项合并得到 5,10,15,...，与第 3 台机器的序列合并之后，最终序列的第一项就是答案。

由于答案不会超过 a_n，序列的长度就是根号级别。时间复杂度 O(n\sqrt{a_n})。代码如下，可供参考：

::::info[code]

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e4+10;
int n,a[N],b[N],totc,totd;long long c[M],d[M],tmp[M]; 
void merge(){
    int i=1,j=1,tot=0;
    while(i<=totc&&j<=totd){
        if(c[i]<d[j])tmp[++tot]=c[i],i++;
        else tmp[++tot]=d[j],j++;
    }
    while(i<=totc)tmp[++tot]=c[i],i++;
    while(j<=totd)tmp[++tot]=d[j],j++;
    for(int k=1;k<=tot;k++)c[k]=tmp[k];
    totc=tot;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        int now=a[i],sum=0;totd=0;
        for(int j=1;;j++){
            sum+=now;
            if(sum>a[n])break;
            d[++totd]=now;
            now+=b[i];
        }
        if(i==1){for(int j=1;j<=totd;j++)c[++totc]=d[j];}
        else{
            int netot=0;
            for(int j=1;j<=totc;j++){
                if(j*2>totc)break;
                c[j]=c[j*2-1]+c[j*2];
                netot=j;
            }
            totc=netot;
            merge();
        }
    } 
    cout<<c[1];
    return 0;
}

::::