时间：2022.1.17——2022.1.23

---

一、刷题记录

1. P1271 【深基9.例1】选举学生会

using namespace std;
int a[1005]={0};
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int x;cin>>x;a[x]++;}for(int i=1;i<=n;i++){while(a[i]){cout<<i<<' ';a[i]--;}}return 0;
}

2. P1177 【模板】快速排序        本题使用传统的快排会出现TLE，将二分法查找应用进去就可以加快程序的运行。

#include "iostream"
using namespace std;
int a[100000];
void quickSort(int left,int right)
{int i=left,j=right;int basic=a[(i+j)/2];while(i<=j){for(;a[j]>basic;j--);for(;a[i]<basic;i++);if(i<=j){swap(a[i],a[j]);    i++;    j--;}}if(left<j) quickSort(left,j);if(i<right) quickSort(i,right);
}int main()
{int N;cin>>N;for(int i=0;i<N;i++){cin>>a[i];}quickSort(0,N-1);for(int i=0;i<N;i++)cout<<a[i]<<' ';cout<<endl;return 0;
}

3. P1923 【深基9.例4】求第 k 小的数        这道题依旧采用二分快排，再判断k值与基准值的位置关系，选择性的排序，减少程序的运行时间。但是这样的话依旧会出现一个TLE，于是我发现scanf和printf的运行速度是比cin与cout的运行速度是快。全部换成scanf和printf就可以AC了。

#include "iostream"
using namespace std;
long a[5000005];
int k;
void quickSort(int left,int right)
{int i=left,j=right;long basic=a[(i+j)/2];while(i<=j){for(;a[j]>basic;j--);for(;a[i]<basic;i++);if(i<=j){swap(a[i],a[j]);    i++;    j--;}}if(k<=j)    quickSort(left,j);else if(k>=i)   quickSort(i,right);else{printf("%ld",a[j+1]);exit (0);}
}int main()
{int N;scanf("%d %d",&N,&k);for(int i=0;i<N;i++){scanf("%ld",&a[i]);}quickSort(0,N-1);
}

4. P1059 [NOIP2006 普及组] 明明的随机数        这题无难度，直接“对号入座”再判断输出即可。

#include "iostream"
using namespace std;
int a[1005];
int main()
{int N,M=0;cin>>N;while(N--){int x;cin>>x;if(a[x]==0){    a[x]=1; M++;    }}cout<<M<<endl;for(int i=1; i<=1000; i++){if(a[i]==1)cout<<i<<' ';}cout<<endl;return 0;
}

5. P1093 [NOIP2007 普及组] 奖学金        这题直接使用algorithm库函数下sort函数对数组进行条件排序即可。

#include "iostream"
#include "algorithm"
using namespace std;
struct student{int num,ach,chinese;
}stu[301];
bool sort2(student x,student y){if(x.ach!=y.ach)    return (x.ach>y.ach);if(x.chinese!=y.chinese)    return (x.chinese>y.chinese);if(x.num!=y.num)    return (x.num<y.num);return 0;
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;stu[i].num=i;     stu[i].ach=a+b+c;     stu[i].chinese=a;}sort(stu+1,stu+n+1,sort2);for(int i=1;i<=5;i++)cout<<stu[i].num<<' '<<stu[i].ach<<endl;return 0;
}

6. P1781 宇宙总统        因为票数的数据可能达到100位，所以创建一个结构体变量将票数定义为string型，依旧使用sort函数。

#include "iostream"
#include "algorithm"
using namespace std;
struct people{string s;int num;
}a[21];
bool sort2(people x,people y)
{if(x.s==y.s)    return true;else if((x.s).length()!=(y.s).length()) return x.s.length()>y.s.length();else return x.s>y.s;
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){a[i].num=i;cin>>a[i].s;}sort(a+1,a+n+1,sort2);cout<<a[1].num<<endl<<a[1].s<<endl;return 0;
}

7. P2676 [USACO07DEC]Bookshelf B        

#include "iostream"
#include "algorithm"
using namespace std;
int a[20005];
bool sort2(int a1,int a2)
{return a1>a2;
}
int main()
{int N,B,sum=0;cin>>N>>B;for(int i=1;i<=N;i++)cin>>a[i];sort(a+1,a+N+1,sort2);int i=1;while(sum<B){sum+=a[i];i++;        }cout<<i-1<<endl;return 0;
}

8. P1116 车厢重组        只能相邻数据俩俩交换，简单的冒泡法就可以实现。（其实并不需要排序，仅统计次数就可以了）

#include "iostream"
using namespace std;
int a[1000];
int main()
{int N,sum=0;cin>>N;for(int i=0;i<N;i++)cin>>a[i];for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)if(a[i]>a[j])   sum++;cout<<sum<<endl;return 0;
}

9. P1152 欢乐的跳        这一题我们可以建一个数组b[]，用来存放a[]数据中两相邻数的差出现的次数，因为n个数据必定有n-1个相邻数的差，所以我最后只需要统计b数组中所有数据出现的次数的总和sum，看sum是否等于n-1即可。

#include "iostream"
using namespace std;
int a[1001],b[1000]={0};
int main()
{int n,sum=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int t=abs(a[i]-a[i+1]);if(0<t&&t<=(n-1))b[t]++;}for(int i=1;i<1000;i++)sum+=b[i];if(sum==(n-1))  cout<<"Jolly"<<endl;else    cout<<"Not jolly"<<endl;return 0;
}

10. P1068 [NOIP2009 普及组] 分数线划定        这一题并不难 看清题目很容易AC

#include "iostream"
#include "algorithm"
using namespace std;
struct exam{int num;int f;
} a[50001];
bool sort2(exam x,exam y)
{if(x.f!=y.f)  return x.f>y.f;else    return x.num<y.num;
}
int main()
{int n,m,i;cin>>n>>m;for(i=1;i<=n;i++){cin>>a[i].num>>a[i].f;}sort(a+1,a+n+1,sort2);m=m*1.5;for(i=1;a[i].f>=a[m].f&&i<=n;i++);cout<<a[m].f<<' '<<i-1<<endl;for(i=1;a[i].f>=a[m].f&&i<=n;i++)cout<<a[i].num<<' '<<a[i].f<<endl;return 0;
}

11. P5143 攀爬者        

#include "iostream"
#include "algorithm"
#include "math.h"
using namespace std;
struct xyz{int x,z,y;
}a[50001];
bool sort2(xyz n,xyz m){return (n.z<m.z);
}
int main()
{int N;double f=0;cin>>N;for(int i=1;i<=N;i++){cin>>a[i].x>>a[i].y>>a[i].z;}sort(a+1,a+N+1,sort2);for(int i=1;i<N;i++)f+=sqrt(pow(a[i].x-a[i+1].x,2)+pow(a[i].y-a[i+1].y,2)+pow(a[i].z-a[i+1].z,2));printf("%.3lf\n",f);return 0;
}

12. P1104 生日

#include "iostream"
#include "algorithm"
using namespace std;
struct stu{string name;int y,m,d,num;
}a[100];
bool sort2(stu x,stu y){if(x.y!=y.y)    return x.y<y.y;else if(x.m!=y.m)   return x.m<y.m;else if(x.d!=y.d)   return x.d<y.d;else return x.num>y.num;
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i].name>>a[i].y>>a[i].m>>a[i].d;a[i].num=i;}sort(a,a+n,sort2);for(int i=0;i<n;i++)cout<<a[i].name<<endl;return 0;
}

13. P1012 [NOIP1998 提高组] 拼数        这一题按照以前sort函数写return x>y; 的话最后会有一个WA，因为输入数据类型为string，当输入321   32   1这组数据时，return x>y;会判定321>32，即结果为：321321，显然是不对的，所以使用return x+y>y+x;这样的话就会整体判断32132与32321的大小，就不会出错了。

#include "iostream"
#include "algorithm"
using namespace std;
string a[20];
bool sort2(string x,string y){return x+y>y+x;
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n,sort2);for(int i=0;i<n;i++)cout<<a[i];cout<<endl;return 0;
}

---

二、个人总结

1. 经过这一周的训练，我已经基本会使用sort函数与快排了，虽然会使函数更简便，但也并没有快排的运行速度快，所以有时候还是要选择性的使用各种函数与算法。

2. 本周整体来说并不是很难的，所以刷完之后对于排序的各种算法和函数还需要找更多的题目来巩固。

3. 对于部分的题即使是用了算法也可能会TLE，所以对传统算法也需要进行优化。