当前位置 : 主页 > 编程语言 > 其它开发 >

刷题记录

来源:互联网 收集:自由互联 发布时间:2022-05-30
代码源 每日一题 切割 洛谷 P6033 合并果子贪心 桶排On和Ologn两种解法 ​ 题目链接: 切割 - 题目 - Daimayuan Online Judge 数据加强版链接: [NOIP2004 提高组] 合并果子 加强版 - 洛谷 题目描述
代码源 每日一题 切割 洛谷 P6033 合并果子贪心 桶排 On和Ologn两种解法

 题目链接:切割 - 题目 - Daimayuan Online Judge

数据加强版链接: [NOIP2004 提高组] 合并果子 加强版 - 洛谷

题目描述

有一个长度为 ∑ai 的木板,需要切割成 n 段,每段木板的长度分别为 a1,a2,…,an。

每次切割,会产生大小为被切割木板长度的开销。

请你求出将此木板切割成如上 nn 段的最小开销。

输入格式

第 1 行一个正整数表示 n。

第 2 行包含 n 个正整数,即 a1,a2,…,an。

输出格式

输出一个正整数,表示最小开销。

数据范围

对于全部测试数据,满足 1≤n,ai≤10^5。

样例输入:

5

5 3 4 4 4

样例输出:

47 

nlogn解法 

核心思想:贪心

正向考虑题意的话,需要每次将长木板较平均的分割成两块,再每次分割出里面最小的,怎么才最平均呢?还得找最大值?个人觉得不是那么好处理,可以考虑下逆向思维,转换一下题意。 

如何转换题意呢?将一块长木板分割为n段,每次的花费为被分割的木板长度,可以等价于被分割成的两块合成一块时,花费为合成的两块的长度和,便转化成了怎样使它合并成一块的花费最小问题。(举个例子,就比如一个长为4的分成一个1一个3,花费为4,跟一个1和一个3合并成一个4,花费为1+3时等价的)

思路:

考虑每次取出两个最小的合成一个更大的,直到最后只剩一个。

证明:

怎么证明这个贪心是对的呢?我们可以假设有三个木块a1<a2<a3,如果取a1,a2合并,需要的花费为(a1+a2)+(a1+a2+a3),如果不取两个最小的,而取a2,a3,需要花费为(a2+a3)+(a2+a3+a1)显然比第一种要大。那么如何推广到一般情况呢?我们可以这样想,合并了两个之后,费用肯定要加上两个的和,两个合并成的一个肯定还需要与其他的合并,而用递归去想这一部分的花费可以看成是大小固定的,就是说你合并成的还需要去和其他的合并求和,而最终下次合并的和是相同的,那么让两个合并的花费尽量小,花费不就小了吗?

代码实现

怎样每次找到两个最小的呢,并加入合并成的那个?我们考虑使用STL自带的最小堆-优先队列priority_queue。

复杂度分析:

优先队列的插入查询均为logn,复杂度为O(n)*O(logn)即O(nlogn)。

代码: 

#include <bits/stdc++.h>
using namespace std;
#define int long long                             //会爆int,所以改为了longlong
priority_queue<int, vector<int>, greater<int>> q; //小根堆
int n, ans;
signed main()
{
    scanf("%lld", &n);
    for (; n--;)
    {
        int x;
        scanf("%lld", &x);
        q.push(x); //初始将n个木块加入
    }
    while (q.size() >= 2)
    {
        int x1, x2;
        x1 = q.top(), q.pop(); //取出两次堆顶
        x2 = q.top(), q.pop();
        ans += (x1 + x2);
        q.push(x1 + x2); //加入合并的木块
    }
    cout << ans << "\n";
}
O(n)解法 

 考虑优化掉每次插入查询的logn。每次合并成的新的木板肯定是载增大的,也就是说合成的木板是有序的,那么我们使没有被合并的那些木板变得有序,每次考虑取两者队首元素中较小的,用两个队列维护,因为有序所以队首元素为最小值。对初始队列的排序考虑桶排。可以在On的时间内完成此题了。(洛谷貌似卡读入了,所以加了个快读)

详见代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100009]; //记录大小为i的木板的数量(桶排)
ll ans;
void read(int &x) //优化读入
{
    int f = 1;
    x = 0;
    char s = getchar();
    while (s < '0' || s > '9')
    {
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9')
    {
        x = x * 10 + s - '0';
        s = getchar();
    }
    x *= f;
}
int main()
{
    int n;
    read(n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        read(x);
        a[x]++; //大小为x的数量+1
    }
    queue<ll> pre, added; // pre为原始的木板队列,added为后来合并加入的队列
    for (int i = 1; i <= 100000; i++)
    {
        while (a[i]--) //因为i可能不止一个
        {
            pre.push(i); //放入队列中,使得pre是有序的
        }
    }
    for (int i = 1; i <= n - 1; i++) // n个需要合并n-1次
    {
        ll x1, x2;
        if ((!pre.empty() && !added.empty() && pre.front() < added.front()) || added.empty()) // pre的队首小于added的队首或者added为空
        {
            x1 = pre.front(); //从pre取
            pre.pop();
        }
        else
        {
            x1 = added.front(); //从added取
            added.pop();
        }
        //重复一次操作取x2
        if ((!pre.empty() && !added.empty() && pre.front() < added.front()) || added.empty()) // pre的队首小于added的队首或者added为空
        {
            x2 = pre.front();
            pre.pop();
        }
        else
        {
            x2 = added.front();
            added.pop();
        }
        ans += (x1 + x2);    //加上花费
        added.push(x1 + x2); // added中加入新合成的木板
    }
    cout << ans;
}


上一篇:【K8S】kubernetes 一些概念的介绍
下一篇:没有了
网友评论