目錄
一，排序問題
二，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;
}
};