题解 P4829 【kry loves 2048】

叶小枫 · 2018-09-18 23:04:36 · 题解

一道卡桶排卡的很死的题目

基本思路

首先我们拿到这道题，先来读一遍……读完之后发现这道题好像闹着玩一样，就是每次把最小的那个数乘2就好了。只是有一点需要注意那就是最后一次比较的判断：如果一趟乘2下来后第二大的数字乘上2比最大的那个数还要小，那么就输出最大的那个，之前的就不用管了。

问题实现

为了更好的实现我们的思路，我们可以开一个队列q，类型为long long ：queue<long long> q

说到这个队列里面存的数具体表示什么意义，还真不是一两句话就能说明白的。那么我们暂且抛开对q的具体定义，先来说一说开这个q的目的：

  用来暂存当前已得到的最大数值，在数组待选择的下一个数比队列元素小时使用队列中的元素，并弹出

这样一来咱们的问题实现就很简单了，分为以下步骤：

1. 使用给定的随机数生成器生成数据并存储
2. 排序该数组
3. 向q中推入目前得到的最大数
4. 数组中没有更大的数可以选择时，调用q中元素直到数组元素选完（此时q中仅存的数字就是答案）
5. 输出q.front()

这题做完了

巨大问题

但是我们看到了这一题的数据范围非常不友好：n,m≤10^7 ……

nlogn基本超了十的五次方就炸了，n的话能坚持到六次方 ——jiang25262

那么我们回头来捋一捋我们学过的一些排序算法：

• 冒泡
• 插入
• 选择
• 快排
• 归并
• 基数（太玄学）
• …………

我们发现好像上面说到的方法都最多只能撑到1e5，这样的程序是不会AC的。但是结合我们上述的问题实现分析，我们起码可以写出一个及格（60分）的代码：

60分代码

#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
#define rint register int
using namespace std;
const int maxn=1e7+10;
ll cnt,n,m;
int a[maxn],b[maxn];
queue<ll>q;
void generate_array(int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i]=(x % m+ 1);
    }
}

inline ll get(){
    if(q.empty())
        return a[cnt++];

    ll f=q.front();
    if(cnt==n||a[cnt]>f){
        q.pop();
        return f;
    }

    return a[cnt++];
}

int main(){
    ios::sync_with_stdio(false);//使用最快速的读入（其实没用）
    int seed;
    cin>>n>>m>>seed;
    generate_array(n,m,seed);

    sort(a,a+n);//使用还可以的快排排序

    ll a1,a2;
    for(rint i=1;i<=n-1;i++){
        a1=get();a2=get();
        q.push(max(a1<<1,a2));
    }
    cout<<q.front()<<'\n';
    return 0;
}

问题解决

仔细阅读我们的60分代码我们可以发现一个显而易见的问题，即：该程序的时间复杂度其实就是排序的时间复杂度。因为对于队列的操作都是O(1)的，获取元素的操作是O(n)的，排序的复杂度再低也低不到O(n)以下。故排序复杂度决定了这题的复杂度。

所以我们现在亟待解决的就是排序问题。

分析到现在，想必我们的目的已经非常明确：我们需要一个O(n)的排序算法！

桶排！

桶排的基本思路是这样，我们把它形象化：

  先开一个数组作为一个桶，然后把等待排序的元素倒进桶里。为了维护“倒进去”的过程，我们对于每一个元素按照其数值计数：

b[a[i]]++;//其中a为待排序数组，b为桶

  接着我们需要找到这些数的最大值，从0开始（如果保证数据>0的话）依次枚举数字，以检查桶中是否有这个数字。如果桶中有，就倒出来，有几个就倒几个：

int t=0;
    for(rint i=0;i<=m;++i)
        while(b[i]>=1){
            a[t++]=i;
            b[i]--;
        }

  倒完了，咱们也就排完了。上标准代码：

for(int i=0;i<n;++i)
        b[a[i]]++;
    int t=0;
    for(rint i=0;i<=m;++i)
        while(b[i]>=1){
            a[t++]=i;
            b[i]--;
        }
//其中，n为元素个数，m为这些元素的最大值

桶排就讲完了，讲完了桶排，这一题也就没有什么可以讲的了。我们接下来要做的只是把原来的sort(a,a+n)换成标准桶排就可以了。

这题真正做完，最后奉上AC代码。

AC代码

#include<iostream>
#include<queue>
#define ll long long
#define rint register int
using namespace std;
const int maxn=1e7+10;
ll cnt,n,m;
int a[maxn],b[maxn];
queue<ll>q;
void generate_array(int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i]=(x % m+ 1);
    }
}

inline ll get(){
    if(q.empty())
        return a[cnt++];

    ll f=q.front();
    if(cnt==n||a[cnt]>f){
        q.pop();
        return f;
    }

    return a[cnt++];
}

int main(){
    ios::sync_with_stdio(false);
    int seed;
    cin>>n>>m>>seed;
    generate_array(n,m,seed);

    for(rint i=0;i<n;++i)
        b[a[i]]++;
    int t=0;
    for(rint i=0;i<=m;++i)
        while(b[i]>=1){
            a[t++]=i;
            b[i]--;
        }

    ll a1,a2;
    for(rint i=1;i<=n-1;i++){
        a1=get();a2=get();
        q.push(max(a1<<1,a2));
    }
    cout<<q.front();
    return 0;
}

鸣谢

教会了我桶排的 @晨搏的小迷妹 U84254

部分代码提供 @晨搏的小迷妹 U84254

复杂度简要区分 @jiang25262 U50227

最后宣传一下我们的团队

欢迎加入我们的团队：洛谷团队传送门

刚刚入门的oier们可以在这里得到最基础的技能培训辅导，我们随时可以为入门级的oier们答疑解惑。进入团队即可获得本团队人员录制的线上课程，主要针对竞赛入门向。在语法课程结束后我们会开启算法线上课程，敬请期待！

当然也非常欢迎各路大佬神犇光临出题虐菜（主要是虐我，他们都比我强）

私信我获取团队QQ群号和线上课程地址

感谢阅读