目录
一，排序问题
二，OJ实战
CSU 1009 抛硬币
CSU 1044: 扑克排序
CSU 1254: 开机
CSU 1270: Swap Digits
UVA - 11292 Dragon of Loowater
力扣 767. 重构字符串
一，排序问题
本文是归纳除了田忌赛马、活动安排问题这2类经典的排序类贪心问题之外，其他的排序类贪心问题。
二，OJ实战
CSU 1009 抛硬币
题目：
Description
James得到了一堆有趣的硬币，于是决定用这些硬币跟朋友们玩个小游戏。在一个N行M列的表格上，每一个第i行第j列的格子上都放有一枚James的硬币，抛该硬币正面朝上的概率为Pij，所有抛硬币事件两两之间是相互独立的。
现在，玩家在M列硬币中，从每一列里各选择1枚，共M枚，构成一组。如此重复选择N组出来，且保证被选择过的硬币不能再选。选好组之后，每组的M枚硬币各抛一次，如果都是正面朝上，则该组胜利，总分赢得1分；否则该组失败，总分不加也不减。请问，如果让你自行选择硬币的分组，游戏总得分的数学期望的最大值是多少？
Input
输入有多组数据。每组数据第一行为N和M，1≤N≤100，1≤M≤10，以空格分隔。接下来有N行，每行M个小数，表示表格中对应的Pij。
输入以N=M=0结束，这组数据不输出结果。
Output
对于每组数据，输出对应游戏总得分的数学期望的最大值，四舍五入精确至4位小数。每组数据的输出占一行。
Sample Input
2 3
1.0 1.0 1.0
0.5 0.4 0.3
0 0
Sample Output
1.0600
首先要理解题意，就是把每一列变成任意的顺序，使得各行所有数之积的和最大。
根据排序不等式，这是一个贪心问题，贪心策略是每一列都排序。
代码：
#include<iostream>
using namespace std;
int par(double *list, int p, int r)
{
int i = p, j = r + 1;
double x = list[p];
while (true)
{
while (list[++i] < x && i < r);
while (list[--j]>x);
if (i >= j)break;
double t = list[j];
list[j] = list[i];
list[i] = t;
}
list[p] = list[j];
list[j] = x;
return j;
}
void sort(double *list, int low, int high)
{
if (low < high)
{
double p = par(list, low, high);
sort(list, low, p - 1);
sort(list, p + 1, high);
}
}
int main()
{
int n, m;
while (cin >> n >> m)
{
if (n == 0 && m == 0)break;
double **list = new double*[m];
for (int i = 0; i < m; i++)list[i] = new double[n];
for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> list[j][i];
for (int i = 0; i < m; i++)sort(list[i], 0, n - 1);
double sum = 0;
for (int i = 0; i < n; i++)
{
double t = 1;
for (int j = 0; j < m; j++)t = t* list[j][i];
sum += t;
}
printf("%.4lf\n", sum);
}
return 0;
}
CSU 1044: 扑克排序
题目：
Description
一叠数值不同的扑克牌（不超过13张），每次只能拿最顶端的一张插入到任意位置。至少操作多少次，扑克牌能够从上到下是从大到小的顺序。
Input
多组数据，每组第一行为n，扑克牌个数。第二行n个空格隔开的正整数，（这些数是1~13），为这叠扑克牌从下到上的数值。
Output
每组数据输出一行，至少按规则操作的次数。
Sample Input
3
1 3 2
5
1 3 5 2 6
Sample Output
1
2
代码：
#include<iostream>
using namespace std;
int main()
{
int n, a, b;
while (cin>>n)
{
a = 0;
bool flag = true;
while (n--)
{
cin >> b;
if (flag && a > b)
{
cout << n + 1 << endl;
flag = false;
}
a = b;
}
if (flag)cout << 0 << endl;
}
return 0;
}
CSU 1254: 开机
Description
机房有很多机器，不同机器开机时间不同。已知开始站在1号机器，从一台机器走到另一台机器需要5秒，如何才能用最短的时间打开所有的机器。
Input
每组数据开头一个n表示机器数，接下来n个数表示1~n号机器所需开机时间，以秒为单位。0 < n <= 1000，开机时间为10~60秒。
Output
每组数据输出一行一个数，表示所有机器打开所需最短时间。
Sample Input
3
35
10
30
Sample Output
35
贪心
注意一开始是站在第一个机器
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n, num[1000], ans;
while (cin >> n)
{
for (int i = 0; i < n; i++)cin >> num[i];
sort(num + 1, num + n);
ans = num[0];
for (int i = 1; i < n; i++)if (ans < num[i] + (n - i) * 5)ans = num[i] + (n - i) * 5;
cout << ans << endl;
}
return 0;
}
CSU 1270: Swap Digits
题目：
Description
Now we have a number, you can swap any two adjacent digits of it, but you can not swap more than K times. Then, what is the largest probable number that we can get after your swapping?
Input
There is an integer T (1 <= T <= 200) in the first line, means there are T test cases in total.
For each test case, there is an integer K (0 <= K < 106) in the first line, which has the same meaning as above. And the number is in the next line. It has at most 1000 digits, and will not start with 0.
There are at most 10 test cases that satisfy the number of digits is larger than 100.
Output
For each test case, you should print the largest probable number that we can get after your swapping.
Sample Input
3
2
1234
4
1234
1
4321
Sample Output
3124
4213
4321
思路：贪心
首先尽量把最高位变成最大的数字，再往右一位位一样的操作，直到变换次数用完
代码：
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int T, s, len;
char ch[1001];
cin >> T;
while(T--)
{
cin >> s >> ch;
len = strlen(ch);
for (int i = 0; i < len; i++)
{
if (s <= 0)break;
char max = '0';
int key;
for (int j = i + 1; j < len && j <= i + s; j++)if (max < ch[j])max = ch[j], key = j;
if (max > ch[i])
{
for (int j = key; j > i; j--)ch[j] = ch[j - 1];
ch[i] = max, s -= key - i;
}
}
cout << ch << endl;
}
return 0;
}
UVA - 11292 Dragon of Loowater
题目：
贪心即可，直接用sort排序就可以了。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int ln[20000], lm[20000];
int main()
{
int n, m, sum;
while (cin >> n >> m)
{
if (n == 0)break;
for (int i = 0; i < n; i++)cin >> ln[i];
for (int i = 0; i < m; i++)cin >> lm[i];
sort(ln, ln + n);
sort(lm, lm + m);
sum = 0;
int i, j;
for (i = 0, j = 0; i < n && j < m; j++)if (lm[j] >= ln[i])
{
sum += lm[j];
i++;
}
if (i == n)cout << sum << endl;
else cout << "Loowater is doomed!" << endl;
}
return 0;
}
力扣 767. 重构字符串
题目：
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在[1, 500]区间内。
思路：
分2步，先判断最多的字符是否超过其他所有字符的数量+1，如果超过就无法重构，不超过就可以重构。
其次，按照贪心原则，每次取数量最多的字符即可。
代码：
class Solution {
public:
string reorganizeString(string S) {
int num[26] = { 0 };
int len = S.length();
for (int i = 0; i < len; i++)num[S[i] - 'a']++;
for (int i = 0; i < 26; i++)if (num[i]>(len + 1) / 2)return "";
string ans = S;
char tmp = '0';
for (int i = 0; i < len; i++)
{
int maxNum = 0, maxId = 0;
for (int j = 0; j < 26; j++)
{
if (tmp - 'a' == j)continue;
if (maxNum < num[j])maxNum = num[j], maxId = j;
}
ans[i] = tmp = 'a' + maxId;
num[maxId]--;
}
return ans;
}
};