《算法竞赛进阶指南》0.8总结与练习(2)

心已赠人 2021-11-16 07:42 193阅读 0赞

## 122. 糖果传递 ##

有n个小朋友坐成一圈，每人有a\[i\]个糖果。  
每人只能给左右两人传递糖果。  
每人每次传递一个糖果代价为1。  
求使所有人获得均等糖果的最小代价。

**输入格式**  
第一行输入一个正整数n，表示小朋友的个数。  
接下来n行，每行一个整数a\[i\]，表示第i个小朋友初始得到的糖果的颗数。

**输出格式**  
输出一个整数，表示最小代价。

**数据范围**  
1≤n≤1000000

**输入样例：**  
4  
1  
2  
5  
4

**输出样例：**  
4

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 1000010;
    
    int n;
    LL a[N];
    
    int main()
    {
        scanf("%d", &n);
        LL sum = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            sum += a[i];
        }
        sum /= n; //中位数
        for(int i = n; i > 1; i--)
        {
            a[i] = sum - a[i] + a[i + 1];
        }
        a[1] = 0;
        
        sort(a + 1, a + n + 1);
        LL res = 0;
        
        for(int i = 1; i <= n; i++) res += abs(a[i] - a[(n + 1) / 2]); //上取整 n/2 的上取整 等价于 n+1 / 2 的下取整
        
        cout << res << endl;
        
        return 0;
    }

## 123. 士兵 ##

格格兰郡的N名士兵随机散落在全郡各地。  
格格兰郡中的位置由一对(x,y)整数坐标表示。  
士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的x或y坐标也将加1或减1）。  
现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的y坐标相同并且x坐标相邻。  
请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。  
需注意，两个或多个士兵不能占据同一个位置。

**输入格式**  
第一行输入整数N，代表士兵的数量。  
接下来的N行，每行输入两个整数x和y，分别代表一个士兵所在位置的x坐标和y坐标，第i行即为第i个士兵的坐标(x\[i\],y\[i\])。

**输出格式**  
输出一个整数，代表所有士兵的总移动次数的最小值。

**数据范围**  
1≤N≤10000,  
−10000≤x\[i\],y\[i\]≤10000

**输入样例：**  
5  
1 2  
2 2  
1 3  
3 -2  
3 3

**输出样例：**  
8

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 10010;
    
    int n;
    int x[N], y[N];
    
    int work(int *q) // *q等价于q[0]
    {
        int res = 0;
        sort(q, q + n);
        for(int i = 0; i < n; i++) res += abs(q[i] - q[i / 2]); //下标从0开始 i/2下取整
        return res;
    }
    
    int main()
    {
        cin >> n;
        for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
        
        sort(x, x + n);
        for(int i = 0; i < n; i++) x[i] -= i;
        
        cout << work(y) + work(x) << endl;
        
        return 0;
    }

## 124. 数的进制转换 ##

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。  
这里有62个不同数位\{0-9,A-Z,a-z\}。

**输入格式**  
第一行输入一个整数，代表接下来的行数。  
接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。  
输入进制和输出进制都在2到62的范围之内。  
（在十进制下）A = 10，B = 11，…，Z = 35，a = 36，b = 37，…，z = 61 (0-9仍然表示0-9)。

**输出格式**  
对于每一组进制转换，程序的输出都由三行构成。  
第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。  
第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。  
第三行为空白行。  
同一行内数字用空格隔开。

**输入样例：**  
8  
62 2 abcdefghiz  
10 16 1234567890123456789012345678901234567890  
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2  
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A  
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05  
49 61 1VbDkSIMJL3JjRgAdlUfcaWj  
61 5 dl9MDSWqwHjDnToKcsWE1S  
5 10 42104444441001414401221302402201233340311104212022133030

**输出样例：**  
62 abcdefghiz  
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890  
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2  
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A  
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05  
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj  
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S  
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030  
10 1234567890123456789012345678901234567890

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    int main()
    {
        int T;
        cin >> T;
        while(T --)
        {
            int a, b;
            string a_line, b_line;
            cin >> a >> b >> a_line;
            
            vector<int> number;
            for(auto c : a_line)
            {
                if(c >= '0' && c <= '9') number.push_back(c - '0');
                if(c >= 'A' && c <= 'Z') number.push_back(c - 'A' + 10);
                if(c >= 'a' && c <= 'z') number.push_back(c - 'a' + 36);
            }
            reverse(number.begin(), number.end()); // 从低位到高位存
            
            //短除法
            vector<int> res;
            while(number.size())
            {
                int r = 0; // 上一位的余数 进位 
                for(int i = number.size() - 1; i >= 0; i--)
                {
                    number[i] += r * a; // 当前一位的值 = 上一位的借位 * 进制
                    r = number[i] % b; // 余数 = 当前这一位 / b 
                    number[i] /= b;
                }
                res.push_back(r); // 最后的余数就是转换进制的个位
                //把结果的0删除
                while(number.size() && number.back() == 0) number.pop_back();
            }
            
            reverse(res.begin(), res.end()); 
            for(auto x : res)
            {
                if(x <= 9) b_line += char(x + '0');
                if(x >= 10 && x <= 35) b_line += char(x - 10 + 'A');
                if(x >= 36) b_line += char(x - 36 + 'a');
            }
            
            cout << a << ' ' << a_line << endl;
            cout << b << ' ' << b_line << endl;
            cout << endl;
        }
        return 0;
    }

## 125. 耍杂技的牛 ##

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。  
奶牛们不是非常有创意，只提出了一个杂技表演：  
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。  
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。  
这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。  
一头牛只撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。  
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

**输入格式**  
第一行输入整数N，表示奶牛数量。  
接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。

**输出格式**  
输出一个整数，表示最大风险值的最小可能值。

**数据范围**  
1≤N≤50000,  
1≤Wi≤10,000,  
1≤Si≤1,000,000,000

**输入样例：**  
3  
10 3  
2 5  
3 3

**输出样例：**  
2

#include <iostream>
    #include <algorithm>
    #include <limits.h>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 50010;
    
    int n;
    PII cows[N];
    
    int main()
    {
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            int w, s;
            cin >> w >> s;
            cows[i] = {w + s, w}; //以 w + s 排序 pair 以第一个关键字排序
        }
        
        sort(cows, cows + n);
        
        int sum = 0, res = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            int w = cows[i].second, s = cows[i].first - w;
            res = max(res, sum - s); //首先更新res
            sum += w;
        }
        cout << res << endl;
        return 0;
    }

## 126. 最大的和 ##

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 \* 1或更大的连续子阵列。  
矩形的总和是该矩形中所有元素的总和。  
在这个问题中，具有最大和的子矩形被称为最大子矩形。  
例如，下列数组：

0 -2 -7 0  
9 2 -6 2  
\-4 1 -4 1  
\-1 8 0 -2

其最大子矩形为：

9 2  
\-4 1  
\-1 8

它拥有最大和15。

**输入格式**  
输入中将包含一个N\*N的整数数组。  
第一行只输入一个整数N，表示方形二维数组的大小。  
从第二行开始，输入由空格和换行符隔开的N2个整数，它们即为二维数组中的N2个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。  
数组中的数字会保持在\[-127,127\]的范围内。

**输出格式**  
输出一个整数，代表最大子矩形的总和。

**数据范围**  
1≤N≤100

**输入样例：**  
4  
0 -2 -7 0 9 2 -6 2  
\-4 1 -4 1 -1

8 0 -2

**输出样例：**  
15

#include <iostream>
    #include <algorithm>
    #include <limits.h>
    
    using namespace std;
    
    const int N = 110;
    
    int n;
    int g[N][N];
    
    int main()
    {
        cin >> n;
        for(int i = 1; i <= n; i++) //求前缀和
            for(int j = 1; j <= n; j++)
            {
                cin >> g[i][j];
                g[i][j] += g[i - 1][j];
            }
            
        int res = INT_MIN;
        for(int i = 1; i <= n; i++) //枚举上界
            for(int j = i; j <= n; j++) //枚举下界 j从i开始
                {
                    int last = 0;
                    for(int k = 1; k <= n; k++)
                    {
                        //last存以上一个数结尾的连续最大子矩阵的和，last < 0，负收益，则舍去，赋为0
                        last = max(last, 0) + g[j][k] - g[i - 1][k]; //以第k列为结尾的连续子矩阵最大和，上界为i，下界为j
                        res = max(res, last);
                        
                    }
                }
        cout << res << endl;        
        return 0;        
    }

## 127. 任务 ##

今天某公司有M个任务需要完成。  
每个任务都有相应的难度级别和完成任务所需时间。  
第i个任务的难度级别为yi，完成任务所需时间为xi分钟。  
如果公司完成此任务，他们将获得（500 \* xi+ 2 \* yi）美元收入。  
该公司有N台机器，每台机器都有最长工作时间和级别。  
如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。  
如果任务难度级别超过机器的级别，则机器无法完成次任务。  
每台机器一天内只能完成一项任务。  
每个任务只能由一台机器完成。  
请为他们设计一个任务分配方案，使得该公司能够最大化他们今天可以完成的任务数量。  
如果有多种解决方案，他们希望选取赚取利润最高的那种。

**输入格式**  
输入包含几个测试用例。  
对于每个测试用例，第一行包含两个整数N和M，分别代表机器数量和任务数量。  
接下来N行，每行包含两个整数xi,yi，分别代表机器最长工作时间和机器级别。  
再接下来M行，每行包含两个整数xi,yi，分别代表完成任务所需时间和任务难度级别。

**输出格式**  
对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。

**数据范围**  
1≤N,M≤100000,  
0<xi<1440,  
0≤yi≤100

**输入样例：**  
1 2  
100 3  
100 2  
100 1

**输出样例：**  
1 50004

/*
    1.最大匹配当且仅当没有增广路经
    2.权值最大匹配 带权最大二分图匹配有两种：1.带边权 KM算法完全匹配（没一点都匹配上）
                                            2.点权 贪心，匈牙利算法（按点权重从大到小排序，从大到小去做匈牙利算法 
                                            时间复杂度NM（N为点数，M为边数）
    */
    
    #include <iostream>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    
    typedef long long LL;
    typedef pair<int, int> PII;
    const int N = 100010;
    
    int n, m;
    PII mchs[N], tasks[N];
    
    int main()
    {
        while(cin >> n >> m)
        {
            for(int i = 0; i < n; i++) cin >> mchs[i].first >> mchs[i].second;
            for(int i = 0; i < m; i++) cin >> tasks[i].first >> tasks[i].second;
            
            sort(mchs, mchs + n);
            sort(tasks, tasks + m); //从小到大排序
            
            multiset<int> ys; //可以用相同元素
            LL cnt = 0, res = 0;
            for(int i = m - 1, j = n - 1; i >= 0; i--) //从大到小遍历 i枚举任务，j枚举机器
            {
                int x = tasks[i].first, y = tasks[i].second;
                while(j >= 0 && mchs[j].first >= x) ys.insert(mchs[j --].second); //横坐标大于等于当前任务的机器加入set
                auto it = ys.lower_bound(y); //>=当前任务y值的最小y
                if(it != ys.end())
                {
                    cnt ++;
                    res += 500 * x + 2 * y;
                    ys.erase(it); // 删掉机器
                }
            }
            cout << cnt << ' ' << res <<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wmxnlfd/p/10879500.html