[code source] daily problem segmentation (nlogn & n solution)

Topic link ： cutting - subject - Daimayuan Online Judge

Data enhanced link ： [NOIP2004 Improvement group ] Combine the fruits Enhanced Edition - Luogu

Title Description

There is a length of ∑ai Wooden board , Need to be cut into n paragraph , The length of each section of wood is a1,a2,…,an.

Each cut , There will be an overhead of the size of the length of the board being cut .

Please find out how to cut this board into the above nn The minimum overhead of the segment .

Input format

The first 1 Line a positive integer to represent n.

The first 2 Line inclusion nn A positive integer , namely a1,a2,…,an.

Output format

Output a positive integer , Represents the minimum overhead .

Data range

For all test data , Satisfy 1≤n,ai≤10^5.

The sample input ：

5

5 3 4 4 4

Sample output ：

47 

nlogn solution  

The core idea ： greedy

If you are thinking about the meaning of the question , It is necessary to divide the long board into two pieces evenly at a time , Divide the smallest one at a time , How to be the most average ？ You have to find the maximum ？ Personally, I don't think it's so easy to deal with , Consider reverse thinking , Change the meaning of the question . 

How to change the meaning of the question ？ Divide a long board into n paragraph , The cost of each time is the length of the divided board , It can be equivalent to when two pieces are divided into one , The cost is the length of the two pieces combined and , It turns into the problem of how to minimize the cost of merging it into one piece .（ for instance , For example, a person with a length of 4 Divided into one 1 One 3, Cost is 4, With one 1 And a 3 Merge into one 4, Cost is 1+3 Time is equivalent to ）

Ideas ：

Consider taking out the two smallest ones at a time to synthesize a larger one , Until there was only one left .

prove ：

How to prove this greed is right ？ We can assume that there are three pieces of wood a1<a2<a3, If you take a1,a2 Merge , The cost required is (a1+a2)+(a1+a2+a3), If you don't take the two smallest , And take a2,a3, It costs (a2+a3)+(a2+a3+a1) Obviously bigger than the first . So how to extend it to the general situation ？ We can think of it this way , After merging the two , The cost must add the sum of two , One of the two combined must also be combined with the other , The cost of using recursion to think about this part can be regarded as a fixed size , That is to say, what you merge into still needs to merge and sum with others , In the end, the and of the next merger are the same , So let the cost of merging the two be as small as possible , Isn't the cost small ？

Code implementation

How to find the two smallest at a time , And join the merged ？ We consider using STL The smallest heap that comes with it - Priority queue priority_queue.

Complexity analysis ：

The insertion queries of the priority queue are logn, The complexity is O(n)*O(logn) namely O(nlogn).

Code ： 

#include <bits/stdc++.h>
using namespace std;
#define int long long                             // Explosive int, So change it to longlong
priority_queue<int, vector<int>, greater<int>> q; // Heap 
int n, ans;
signed main()
{
    scanf("%lld", &n);
    for (; n--;)
    {
        int x;
        scanf("%lld", &x);
        q.push(x); // The initial will be n Add a piece of wood to 
    }
    while (q.size() >= 2)
    {
        int x1, x2;
        x1 = q.top(), q.pop(); // Take out the top twice 
        x2 = q.top(), q.pop();
        ans += (x1 + x2);
        q.push(x1 + x2); // Add the combined wood block 
    }
    cout << ans << "\n";
}

O(n) solution  

  Consider optimizing the number of queries inserted each time logn. Every time the new board is combined, the load must be increased , That is to say, the synthetic boards are orderly , So let's make those boards that haven't been merged orderly , Consider taking the smaller of the two team head elements each time , Maintain... With two queues , Because of order, the first element of the team is the minimum . For the sorting of the initial queue, consider the bucket row . Can be in On I have finished this problem in time .（ Lo Gu seems to have read in , So I added a quick read ）

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100009]; // The record size is i The number of boards （ Bucket row ）
ll ans;
void read(int &x) // Optimize read in 
{
    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]++; // The size is x The number of +1
    }
    queue<ll> pre, added; // pre For the original plank queue ,added Queue added for later merge 
    for (int i = 1; i <= 100000; i++)
    {
        while (a[i]--) // because i There may be more than one 
        {
            pre.push(i); // Put it in the queue , bring pre Is ordered 
        }
    }
    for (int i = 1; i <= n - 1; i++) // n Need to merge n-1 Time 
    {
        ll x1, x2;
        if ((!pre.empty() && !added.empty() && pre.front() < added.front()) || added.empty()) // pre Our team leader is less than added The head of the team or added It's empty 
        {
            x1 = pre.front(); // from pre take 
            pre.pop();
        }
        else
        {
            x1 = added.front(); // from added take 
            added.pop();
        }
        // Repeat the operation to get x2
        if ((!pre.empty() && !added.empty() && pre.front() < added.front()) || added.empty()) // pre Our team leader is less than added The head of the team or added It's empty 
        {
            x2 = pre.front();
            pre.pop();
        }
        else
        {
            x2 = added.front();
            added.pop();
        }
        ans += (x1 + x2);    // Plus the cost 
        added.push(x1 + x2); // added Add the newly synthesized wood board 
    }
    cout << ans;
}