片頭
嗨咯~小伙伴們!今天我們來一起學習算法和貪心思維,準備好了嗎?咱們開始咯!
第1題? 數位排序
對于這道題,我們需要自己寫一個排序算法,也就是自定義排序,按照數位從小到大進行排序。
舉一個例子唄:假設我們從1~13,對這13個數字進行數位排序
數字 | 數位和 |
1 | 1 |
2 | 2 |
3 | 3 |
4 | 4 |
5 | 5 |
6 | 6 |
7 | 7 |
8 | 8 |
9 | 9 |
10 | 1 |
11 | 2 |
12 | 3 |
13 | 4 |
從上述表格中,我們可以看出:
①1~13這13個數字,最大的數位和為9。
②1和10的數位和相同,均為1;2和11的數位和相同,均為2;3和12的數位和相同,均為3;4和13的數位和相同,均為4。
③由此可以得出,1~13的排序為:1,10,2,11,3,12,4,13,5,6,7,8,9。第5個數為3。
理解了題意,有什么思路呢?
我們可以先定義num數組,將1~n每個數字對應的數位和存儲起來
int num[10000086];int n;cin >> n;for (int i = 1; i <= n; i++) {int temp = i;while (temp > 0) {int ge = temp % 10;num[i] += ge; //num數組存儲1~n個數的數位和temp = temp / 10;}}
把這n個數字的數位和存儲起來后,我們需求出當前這n個數字中最大的數位和。
//遍歷num數組,求出最大的數位和int maxnum = 0;for (int i = 1; i <= n; i++) {maxnum = max(maxnum, num[i]);}
接下來就是重頭戲啦:按照數位和從小到大進行排序
外層循環從1~maxnum,表示數位和的取值范圍;內層循環從1~n,表示共有n個數參加數位排序
//按照數位和從小到大進行排序int cnt = 1;//計數器,標記當前數在哪個位置for (int j = 1; j <= maxnum; j++) {for (int i = 1; i <= n; i++) {if (num[i] == j) {res[cnt++] = i;}}}
按照數字和從小到大排序數字:
1. cnt = 1: 計數器,表示res數組中下一個要填充的位置
2. 外層循環 j 從 1 到 maxnum (所有可能的數字和);內層循環 i 從 1 到 n (所有數字)
3. 如果數字 i 的數字和等于當前 j?,就把 i 放入 res 數組
這樣得到的res數組就是按數字和排序的結果,數字和相同的保持原始順序
?最后輸出排序后第m個數字即可。
//輸出第m個元素cout << res[m] << endl;
okk,整體代碼如下:
#include<iostream>
using namespace std;//數位排序int n;
int m;int num[10000086];
int res[10000086];int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int temp = i;while (temp > 0) {int ge = temp % 10;num[i] += ge; //num數組存儲1~n個數的數位和temp = temp / 10;}}//遍歷num數組,求出最大的數位和int maxnum = 0;for (int i = 1; i <= n; i++) {maxnum = max(maxnum, num[i]);}//按照數位和從小到大進行排序int cnt = 1;//計數器,標記當前數在哪個位置for (int i = 1; i <= maxnum; i++) {for (int j = 1; j <= n; j++) {if (num[j] == i) {res[cnt++] = j;}}}//輸出第m個元素cout << res[m] << endl;return 0;
}
如果對以上代碼有疑問的話,不妨看看下面這段文字描述:?
?第2題? 封閉圖形的個數
對于這道題,咱們可以先定義num數組,把數字0~9的封閉圖形的個數存起來。
int cnt[10]; //全局數組,用于存儲每個數字的"圓圈"數量//定義從0~9每個數字中圓圈的個數cnt[0] = 1, cnt[1] = 0, cnt[2] = 0, cnt[3] = 0, cnt[4] = 1;cnt[5] = 0, cnt[6] = 1, cnt[7] = 0, cnt[8] = 2, cnt[9] = 1;
?輸入n個數
const int N = 2e5 + 10; //定義常量N為200000,作為數組大小int a[N];int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}
接下來是重點:如何將數字按照封閉圖形的個數進行排序~
和上一道題類似,只不過是根據當前最后1位數字獲取該數字在num數組中的映射。
bool cmp(int a,int b) {int A = a, B = b; //復制a和b的值,避免修改原值int cnt_a = 0, cnt_b = 0; //初始化兩個數字的圓圈總數//循環計算數字a和b中每個數字位的圓圈數量總和while (A > 0) {int ge = A % 10; //獲取數字的個位數cnt_a += cnt[ge]; //cnt[ge]: 獲取該數字的圓圈數量A = A / 10; //去掉已經處理的個位數}while (B > 0) {int r = B % 10;cnt_b += cnt[r];B = B / 10;}//如果兩個數字的圓圈總數相同,按數字本身的大小升序排序//如果圓圈數量不同,按圓圈數量升序排序if (cnt_a == cnt_b) return a < b; // 圓圈個數相等時比較數值else return cnt_a < cnt_b; // 圓圈個數不等時比較圓圈數量
}
歐克,我們寫好自定義的排序后,接著就可以利用sort函數進行排序啦~
/*使用STL的sort函數進行排序a+1:從數組的第1個元素開始a+n+1:到數組的第n個元素結束cmp :使用自定義的比較函數進行排序*/sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}
okk,本道題完整代碼如下:
#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10; //定義常量N為200000,作為數組大小
int cnt[10]; //全局數組,用于存儲每個數字的"圓圈"數量
int a[N]; //存儲輸入的數字數組bool cmp(int a,int b) {int A = a, B = b; //復制a和b的值,避免修改原值int cnt_a = 0, cnt_b = 0; //初始化兩個數字的圓圈總數//循環計算數字a和b中每個數字位的圓圈數量總和while (A > 0) {int ge = A % 10; //獲取數字的個位數cnt_a += cnt[ge]; //cnt[ge]: 獲取該數字的圓圈數量A = A / 10; //去掉已經處理的個位數}while (B > 0) {int r = B % 10;cnt_b += cnt[r];B = B / 10;}//如果兩個數字的圓圈總數相同,按數字本身的大小升序排序//如果圓圈數量不同,按圓圈數量升序排序if (cnt_a == cnt_b) return a < b; // 圓圈個數相等時比較數值else return cnt_a < cnt_b; // 圓圈個數不等時比較圓圈數量
}int main() {//定義從0~9每個數字中圓圈的個數cnt[0] = 1, cnt[1] = 0, cnt[2] = 0, cnt[3] = 0, cnt[4] = 1;cnt[5] = 0, cnt[6] = 1, cnt[7] = 0, cnt[8] = 2, cnt[9] = 1;int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}/*使用STL的sort函數進行排序a+1:從數組的第1個元素開始a+n+1:到數組的第n個元素結束cmp :使用自定義的比較函數進行排序*/sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}return 0;
}
?如果看不懂以上代碼,不如看看下面這段描述:
小貼士:
第3題? 三國游戲
分析題意:
-
三個國家初始得分均為0
-
每個事件會給三個國家帶來不同的得分
-
一個國家獲勝的條件是該國得分 > 其他兩國得分之和
-
目標是找出能讓某個國家獲勝的最多事件數
對于這道題,我們可以先輸入n個事件分別對魏國,蜀國,吳國的得分
typedef long long ll; // 使用long long防止整數溢出const int N = 1e5 + 100; // 最大事件數int A[N], B[N], C[N]; // 存儲三個國家每個事件的得分cin >> n;//輸入原始數據//A、B、C分別存儲魏蜀吳3個國家發生對應事件增加的得分for (int i = 1; i <= n; i++) cin >> A[i]; //魏國for (int i = 1; i <= n; i++) cin >> B[i]; //蜀國for (int i = 1; i <= n; i++) cin >> C[i]; //吳國
接下來就該我們來實現當其中1個國家獲勝時,最多發生了多少個事件?
首先,我們定義weight[N]數組,用來存儲每個事件對某個國家的“純貢獻"
int weight[N]; // 存儲每個事件對某個國家的"純貢獻"
我們需要格外注意的是:計算下一個國家的純貢獻值時,必須把當前的weight數組里面的值清空
memset(weight,0,sizeof(weight)); //將weight數組里面的原始數據清空
對于n個事件,每個事件對某個國家的"純貢獻" = 事件對該國家的得分與其他國家得分之差。
舉個例子唄~? 假設發生事件 i ,X得4分,Y得2分,Z得1分,可知 4-2-1>0,X獲勝
//計算每個事件對a的純貢獻for (int i = 1; i <= n; i++) {//假設a[i]=7,b[i]=2,c[i]=2,則發生i事件對a的純貢獻是7-2-2=3//可以理解為該發生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}
我們再將每個事件對a的純貢獻,進行從大到小的排序
bool cmp(int a, int b) //從大到小進行排序{return a > b;}//將純貢獻按從大到小進行排序sort(weight + 1, weight + n + 1, cmp);
定義變量sum,初始值為0,用來表示累加當前的總貢獻。定義變量ans,初始值為0,用來記錄可以發生多少事件使a>b+c。
依次循環遍歷n個事件對a的純貢獻,用sum累加每個事件對a的純貢獻,如果每次累加的結果使sum>0,那么ans++,直到sum<0,跳出循環。最后返回結果。
ll sum = 0; //累加當前的總貢獻 int ans = 0; //記錄可以發生多少事件使a>b+cfor (int i = 1; i <= n; i++) {sum += weight[i]; //累加貢獻if (sum > 0) ans++; //累計貢獻嚴格大于0,計數+1else break; //若不大于0,由于序列遞減//后面只會越來越小,直接退出}return ans; //將事件數返回
此外,我們必須考慮特殊情況:當ans==0時,直接返回-1
if (ans == 0) return -1; //1個事件都不能發生,返回-1
okk,關于自定義排序的完整代碼如下:
typedef long long ll; // 使用long long防止整數溢出const int N = 1e5 + 100; // 最大事件數
int A[N], B[N], C[N]; // 存儲三個國家每個事件的得分
int weight[N]; // 存儲每個事件對某個國家的"純貢獻"int n;bool cmp(int a, int b) //從大到小進行排序
{return a > b;
}int solve(int a[], int b[], int c[]) //a獲勝,發生最多的事件數
{ll sum = 0; //累加當前的總貢獻//將weight數組里面的原始數據清空memset(weight, 0, sizeof(weight));//計算每個事件對a的純貢獻for (int i = 1; i <= n; i++) {//假設a[i]=7,b[i]=2,c[i]=2,則發生i事件對a的純貢獻是7-2-2=3//可以理解為該發生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}//將純貢獻按從大到小進行排序sort(weight + 1, weight + n + 1, cmp);//記錄可以發生多少事件使a>b+cint ans = 0;for (int i = 1; i <= n; i++) {sum += weight[i]; //累加貢獻if (sum > 0) ans++; //累計貢獻嚴格大于0,計數+1else break; //若不大于0,由于序列遞減//后面只會越來越小,直接退出}if (ans == 0) return -1; //1個事件都不能發生,返回-1return ans; //將事件數返回
}
我們在main函數中調用solve函數,計算魏國,蜀國,吳國能獲勝的最多事件數。
魏國獲勝的條件是:魏國得分 > 蜀國+吳國得分? -->? ?a?> b?+ c? -->? a?- b - c > 0
蜀國獲勝的條件是:蜀國得分 > 魏國+吳國得分? -->? ?b?> a?+ c? -->? b?- a?- c > 0
吳國獲勝的條件是:吳國得分 > 魏國+蜀國得分? -->? ?c?> a?+ b??-->? c?- a?- b?> 0
int ret1 = solve(A, B, C); //假設魏國獲勝,發生最多的事件數int ret2 = solve(B, A, C); //假設蜀國獲勝,發生最多的事件數int ret3 = solve(C, A, B); //假設吳國獲勝,發生最多的事件數
?最后求出最大值即可。
int MAX = max(ret1, max(ret2, ret3)); //三者取最大值即可cout << MAX << endl; //將最終結果輸出
okk,這道題的整體代碼如下:
//三國游戲
//對于X、Y、Z三個國家,X獲勝的條件為 X>Y+Z
//初始時,三者得分均為0
//故X能否獲勝完全取決于每個事件對應的得分與其他國家得分之差
//假設發生事件i,X得4分,Y得2分,Z得1分,可知 4-2-1>0,X獲勝
//若要求某個國家獲勝所發生的最多事件,只需處理每個事件對該國家的純貢獻即可
//所謂純貢獻就是該事件對該國家的得分與其他國家得分之差,只要大于0即說明可獲性
//計算每個事件對該國家的純貢獻并從大到小排序,依次累加貢獻
//只要總的貢獻仍然大于0,就說明當前事件是可以發生的,計數值+1
//依次枚舉3個國家,比較出可發生的事件數的最大值即為答案#include <bits/stdc++.h>
using namespace std;typedef long long ll; // 使用long long防止整數溢出const int N = 1e5 + 100; // 最大事件數
int A[N], B[N], C[N]; // 存儲三個國家每個事件的得分
int weight[N]; // 存儲每個事件對某個國家的"純貢獻"int n;bool cmp(int a, int b) //從大到小進行排序
{return a > b;
}int solve(int a[], int b[], int c[]) //a獲勝,發生最多的事件數
{ll sum = 0; //初始化累計純貢獻總和(用long long防溢出)memset(weight, 0, sizeof(weight)); //將weight數組里面的原始數據清空//計算每個事件對a的純貢獻for (int i = 1; i <= n; i++) {//假設a[i]=7,b[i]=2,c[i]=2,則發生i事件對a的純貢獻是7-2-2=3//可以理解為該發生事件使a比b+c的得分高了3weight[i] = a[i] - b[i] - c[i];}//將純貢獻按從大到小進行排序sort(weight + 1, weight + n + 1, cmp);//記錄可以發生多少事件使a>b+cint ans = 0;for (int i = 1; i <= n; i++) {sum += weight[i]; // 累加當前事件的純貢獻if (sum > 0) ans++; // 如果累加后總貢獻仍為正,則這個事件可以被選擇,計數器+1else break; // 如果總貢獻≤0,立即終止循環//(后續事件純貢獻更小,只會讓總和更小)}if (ans == 0) return -1; //1個事件都不能發生,返回-1return ans; //將事件數返回
}int main() {cin >> n;//輸入原始數據//A、B、C分別存儲魏蜀吳3個國家發生對應事件增加的得分for (int i = 1; i <= n; i++) cin >> A[i]; //魏國for (int i = 1; i <= n; i++) cin >> B[i]; //蜀國for (int i = 1; i <= n; i++) cin >> C[i]; //吳國int ret1 = solve(A, B, C); //假設魏國獲勝,發生最多的事件數int ret2 = solve(B, A, C); //假設蜀國獲勝,發生最多的事件數int ret3 = solve(C, A, B); //假設吳國獲勝,發生最多的事件數int MAX = max(ret1, max(ret2, ret3)); //三者取最大值即可cout << MAX << endl; //將最終結果輸出return 0;
}
如果對上述代碼有疑問,不妨看看下面的解釋~?
?第4題? 錯誤票據
?這道題,需要我們找出重復和缺失的數。因為題目明確告訴我們:讀取N行數據,每行數據長度不等。因此,我們可以使用vector容器來動態存儲元素。
vector<int> v; //動態數組int n; //輸入n行cin >> n;
?我們可以使用for循環來讀取這n行數據,將元素尾插到vector容器中。如果遇到'\n',那么立即停止對這一行的讀取。
for (int i = 1; i <= n; i++) //總共輸入n行{int x;while (cin >> x) //讀取每行中的每個數字,遇到Ctrl+Z才結束{v.push_back(x); //將數字添加到動態數組v中if (cin.get() == '\n') break; //遇到'\n',停止對這一行進行讀取}}
接下來我們對vector容器中的元素按照從小到大的順序排序:
sort(v.begin(), v.end()); //將所有元素從小到大依次排序
排好序后,我們開始尋找重復和缺失的數字。
重復:2個元素相等
缺失:前一個數字+1不等于后一個數字,也就是非連續的。說明這個數字缺失
int a = 0; //用于存儲重復的數字int b = 0; //用于存儲缺失的數字for (int i = 0; i < v.size() - 1 ; i++) // 遍歷排序后的數組{if (v[i] == v[i + 1]) a = v[i]; // 如果發現相鄰數字相同,記錄重復數字if (v[i + 1] == v[i] + 2) b = v[i] + 1; // 如果發現數字間隔為2,記錄中間缺失的數字}cout << b << " " << a << endl; // 輸出缺失數字和重復數字
歐克啦,本道題完整代碼如下:
#include <bits/stdc++.h>
using namespace std;int main() {vector<int> v; //動態數組int n; //輸入n行cin >> n;for (int i = 1; i <= n; i++) //總共輸入n行{int x;while (cin >> x) //讀取每行中的每個數字,遇到Ctrl+Z才結束{v.push_back(x); //將數字添加到動態數組v中if (cin.get() == '\n') break; //遇到'\n',停止對這一行進行讀取}}sort(v.begin(), v.end()); //將所有元素從小到大依次排序int a = 0; //用于存儲重復的數字int b = 0; //用于存儲缺失的數字for (int i = 0; i < v.size() - 1 ; i++) //遍歷排序后的數組{if (v[i] == v[i + 1]) a = v[i]; //如果發現相鄰數字相同,記錄重復數字if (v[i + 1] == v[i] + 2) b = v[i] + 1; //如果發現數字間隔為2,記錄中間缺失的數字}cout << b << " " << a << endl; //輸出缺失數字和重復數字return 0;
}
第5題? 排個序
這道題,其實是冒泡排序的限制版本。冒泡排序可以任意2個數進行交換,但是這道題有限制條件。
代碼如下:
//排個序int a[1010], p[1010], o[1010];//a: 存儲待排序數組
//p: 存儲允許交換的位置
//o: 一維數組,標記哪些位置允許交換int main() {int n, m;cin >> n >> m; //輸入數組長度n和允許交換的數量m//輸入待排序數組for (int i = 1; i <= n; i++) {cin >> a[i];}//輸入并標記允許交換的位置for (int i = 1; i <= m; i++) {cin >> p[i];o[p[i]] = 1; //標記這個位置允許與其下一個位置交換}//單次遍歷的冒泡排序for (int i = 1; i < n; i++) // i<n 防止訪問a[n+1]越界{if (a[i] > a[i + 1]) //如果需要交換{if (o[i] == 1) //檢查是否允許交換{swap(a[i], a[i + 1]); //允許則交換}else {cout << "NO"; //不允許則直接失敗return 0;}}}cout << "YES"; //所有必要條件都允許,排序成功return 0;
}
片尾
今天我們學習了自定義排序和貪心算法。希望看完這篇文章能對友友們有所幫助!!!
求點贊收藏加關注!!!
謝謝大家!!!