洛谷P2945-沙堡-贪心算法

2019-07-23

约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻枪眼中间那部分叫作“城齿”．城墙上一共有N(1≤N≤25000)个城齿，每一个都有一个高度Mi.(1≤Mi≤100000)．现在约翰想把城齿的高度调成某种顺序下的Bi，B2，…，BN(1≤Bi≤100000). -个城齿每提高一个单位的高度，约翰需要X(1≤X≤100)元；每降低一个单位的高度，约翰需要Y(1≤y≤100)元．问约翰最少可用多少钱达到目的．数据保证答案不超过2^31-1．
输入格式：

第1行: 输入三个整数: n， x， y

*第2行到第N+1行: (i+1)行包括两个整数: M_i 和 B_i

输出格式：

一个整数，代表要重修城堡所需的最小金额
样例输入：
3 6 5
3 1
1 2
1 2
样例输出：
11

思路：

第一遍我没有用C++的sort函数做（主要是我不知道枯），我的主要思路是用一个二维数组存储数据，n行2列，第一列用来存原始数据，第二列用来存目标数据，我再用一个循环n遍，每一遍找出这个二维数组第一列和第二列的最大值求差乘上x或者y，然后把这两列对应位置的数置成-1（保证同一个数不会重复运算）。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n, x, y;
    int sum = 0;
    cin >> n >> x >> y;
    int a[25005][2];
    for(int i=0; i<n; i++)
        for(int j=0; j<2; j++)
        {
            cin >> a[i][j];
        }
    for(int i=0; i<n; i++)
    {
        int r, rr;
        cout << "i:" << i << endl;
        int m = -1, mm = -1;
        for(int i=0; i<n; i++)
        {
            if(a[i][0] > m)
            {
                m = a[i][0];
                r = i;
            }
        }   
        cout << "m: " << m << endl; 
        a[r][0] = -1;
        for(int i=0; i<n; i++)
        {
            if(i == 2)
            {
                if(a[i][1]>mm)
            }
            if(a[i][1] > mm)
            {
                mm = a[i][1];
                rr = i;
            }
        }
        a[rr][1] = -1;
        if((m-mm)>0)
        {
            sum += (m-mm) * y;
        }
        else 
            sum += (mm-m) * x; 
    }
    cout << sum;
    return 0;   
}

但这个代码在洛谷上显示超时，接下来用sort函数做：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, x, y;
    int sum = 0;
    cin >> n >> x >> y;
    int a[25005], b[25005];
    for(int i=0; i<n; i++)
    {
        cin >> a[i] >> b[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    for(int i=0; i<n; i++)
    {
        if(a[i] < b[i])
            sum += (b[i]-a[i]) * x;
        else
            sum += (a[i]-b[i]) * y; 
    }
    cout << sum;
    return 0;
}

这个代码时间上也就没有任何问题了，只是要注意用C++的sort函数时要加上头文件<algorithm>；接下来详讲一下sort函数。

sort函数：

用法：
需要头文件<algorithm>
语法描述：sort（begin，end，cmp），cmp参数可以没有，如果没有默认非降序排序。
控制升序排序还是降序排序：
• 升序：sort(begin,end,less<data-type>())
• 降序：sort(begin,end,greater<data-type>())
（include<functional>------>fuctional提供了一堆基于模板的比较函数）
如果没有com函数，默认为非降序排序
引用数据类型string的使用
Exaple Input:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    string str("hello world");
    sort(str.begin(),str.end());
    cout<<str;
    return 0;
 }

Output:空格dehllloorw

使用反向迭代器可以完成逆序排序
Exaple Input:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    string str("hello world");
    sort(str.rbegin(),str.rend());
    cout<<str;
    return 0;
 }

Output: wroolllhde空格

原文链接：https://www.cnblogs.com/TX980502/p/8528840.html