姓名： 杨子阳
赛道： 基础组
类型： 算法技能
题目： 重生之我在xyd学基础算法
今天一觉醒来，发现【01背包】的题目被清空了
不是玩呢，我的搜索、递归、递推、栈、队列、二叉树、树、结构体、排序、贪心、模拟、高精度、枚举、二进制怎么都没了
哎呀！！！！！！！！！！！！！！！！ 
（已红温）
事已至此，只好重学一遍了
第一章：找到一个big big big big box——结构体
让我们请结构体哥哥来介绍一下自己
框架
struct node{
int a;
int b[1005];
void iii(){
cout << "iii";
}
};
我里面基本什么都能装，嵌套自己也行
写我时记得加分号！！！！
调用
node q;
cin >> q.a;
q.iii();
我可以作为一种类型哦（自定义类型）
调用时用我这种类型的变量+一个小点点+我之中的东西
也可以在分号前定义
}q;
我这种类型也可以定义数组：
node arr[1005];
for(int i = 1;i <= n;i++){
cin >> arr[i].a;
}
arr的每一项都是一个我
小贴士：如果我里面中太多东西，建议数组开的小一点，不然会获得专属成就：
\color{purple}{MLE:Memory\ Limit\ Enough\ \ (空间充足)}
好了，恭喜你掌握了结构体，结构体哥哥给了你一个徽章：
下一章：如何将无序变有序——排序
排序是一个大家族，里面有冒泡排序、选择排序、插入排序、桶排序、sort排序，甚至还有结构体排序。
我们这次让sort弟弟来讲一讲它的家族吧
选择排序：
这位兄台的时间复杂度为 O(n^2) ，排序过程：
核心代码：
for(int i = 1;i <= n - 1;i++){
int minn = i;
for(int j = i + 1;j <= n;j++){
if(a[j] < a[minn]){
minn = j;
}
}
swap(a[i],a[minn]);
}
冒泡排序：
他是我的老大哥，时间复杂度也为 O(n^2) ，排序过程：
核心代码：
for(int i = 1;i <= n - 1;i++){
for(int j = 1;j <= n - i;j++){
if(a[j] > a[j + 1])swap(a[j],a[j + 1]);
}
}
插入排序：
这位老兄时间复杂度依旧为 O(n^2) ，排序过程：
核心代码
for(int i=2;i<=n;i++){
for(int j=i;j>=2;j--){
if(a[j]<a[j-1])swap(a[j],a[j-1]);
else break;
}
}
桶排序：
这位兄弟时间复杂度为 O(n + m) ，排序过程：
核心代码
int b[10000005];
for(int i=1;i<=n;i++){
cin >> a;
b[a]++;
}
for(int i=1;i<=n;i++){
while(b[i]>0){
cout<<i<<" ";
b[i]--;
}
}
sort排序：
我可招人喜欢呢！于是我给自己取了个中文名：索特
我的排序过程我都不知道，直接看核心代码吧：
sort(a + 1,a + 1 + n,cmp);
第一项是开始，第二项是结束，第三项是小小触摸屏cmp（控制如何排序）
如果不写cmp，就默认从小到大排序
从大到小排序的cmp:
bool cmp(int a,int b){
return a > b;
}
没错，就这么短
当然也有更稳定的写法死桌子stable：
stable_sort();
结构体排序：
它是我的弟弟，每逢用它都会有我
核心代码：
struct node{
int a,b;
}arr[100005];
bool cmp(node x,node y){
if(x.a == y.a){
return x.b > y.b;
}
return x.a > y.a;
}
int main(){
//输入就自行脑补吧，反正不重要
sort(arr + 1,arr + 1 + n,cmp);
//输出也自行脑补吧，反正不重要
return 0;
}
这里的cmp不能少，不然会获得成就：
\color{gold}{CE:Compile\ Easily（轻松通过编译）}
cmp中的东西可以自行修改哦
好吧看来sort弟弟人狠话不多，就和他自己的代码一样
他送了你一个徽章就走了
下一章：如何做一个贪官——贪心
作者机密
你真的
以为
这么
容易
找到
……
好吧，给你看
作者：贪心哥哥，来讲一讲吧~
贪心：NO！
作者：那这个呢 
贪心： 
我要这么多 
作者：OK！ 
贪心的手机：微信收款5000元
我们也是成功请来了贪心先生，让他来教教我们做贪官并且犯法不犯法
贪官速成法：
打个比方，你要给别人找45元，而你有纸币1、5、10、20元各无限张（别问，问就是贪来的），怎么给别人的纸币数量最少？
答：当然是2张20元和1张5元。
答案：2张20元、0张10元、1张5元、0张1元。
再来大一点，你要给别人找4889元，而你有纸币1、5、10、20、50、100、500、1000元各无限张（别问，问就是贪来的），怎么给别人的纸币数量最少？
答：是4张1000元、1张500元、3张100元…… 
。
答案：4张1000元、1张500元、3张100元、1张50元、1张20元、1张10元、1张5元、4张1元
从大到小找就是这两题的关键！
第二题核心代码：
int coins[15] = {1,5,10,20,50,100,500,1000};
呃，等一下，找不到了
