P1271 【深基9.例1】選舉學生會

P1271 【深基9.例1】選舉學生會 - 洛谷

【方法一】快速排序

使用sort()，注意數組的范圍！！！

#include<bits/stdc++.h>
using namespace std;int a[2000000],n,m;int main()
{cin>>n>>m;for(int i=0;i<m;i++){cin>>a[i];}sort(a,a+m);for(int i=0;i<m;i++){cout<<a[i]<<" ";}return 0;
}

【方法二】桶排序

桶排序（Bucket Sort）是一種基于分配策略的排序算法，其工作原理是將數組分到有限數量的桶子里，然后對每個桶內的元素進行排序（可能再使用其他排序算法或是以遞歸方式繼續使用桶排序），最后合并所有已排序的桶，從而完成整個數據集的排序。

#include<bits/stdc++.h>
using namespace std;int main()
{int n,m,p;cin>>n>>m;int a[1000]={0};        // 以候選人作為“桶”for(int i=0;i<m;i++){cin>>p;a[p]++;}for(int i=1;i<=n;i++){for(int j=0;j<a[i];j++){cout<<i<<' ';}}return 0;
}

P1923 【深基9.例4】求第 k 小的數

P1923 【深基9.例4】求第 k 小的數 - 洛谷

【方法一】快速排序，直接輸出

但是無法通過所有的測試點！！！

#include<bits/stdc++.h>
using namespace std;int main()
{int n,k;cin>>n>>k;int a[5000001]={0};for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);cout<<a[k];return 0;
}

【方法二】根據快排的思想進行二分

在原二分的基礎上可以進行修改：因為每次遞歸都會將數組劃分為三部分，而答案只會在這三部分中的一個，不需要再對其他部分進行搜索，從而達到優化時間復雜度的效果。

#include<bits/stdc++.h>
using namespace std;int x[5000005],k;void qsort(int l,int r)
{int i=l,j=r,mid=x[(l+r)/2];do{while(x[j]>mid){j--;}while(x[i]<mid){i++;}if(i<=j){swap(x[i],x[j]);i++;j--;}}while(i<=j);//快排后數組被劃分為三塊： l<=j<=i<=rif(k<=j){qsort(l,j);			//在左區間只需要搜左區間}else if(i<=k){qsort(i,r);			//在右區間只需要搜右區間}else 					//如果在中間區間直接輸出{printf("%d",x[j+1]);exit(0);}
}int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&x[i]);}qsort(0,n-1);
}

【方法三】利用?nth_element

在 STL 里有?nth_element 函數。它的用法是?nth_element(a+x,a+x+y,a+x+len)。

執行之后數組?a?下標?x?到?x+y?1?的元素都小于?a[x+y]，下標?x+y+1?到?x+len?1?的元素 都大于?a[x+y]，但不保證數組有序。此時?a[x+y]?就是數組區間?x?到?x+len?1?中第?y?小的數，當然也可以自己定義?cmp?函數。

#include<bits/stdc++.h>
using namespace std;int x[5000005],k;int main()
{int n;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&x[i]);}nth_element(x,x+k,x+n);printf("%d",x[k]);
}

P1781 宇宙總統

P1781 宇宙總統 - 洛谷

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;int num;string a[21];string max;cin>>max;for(int i=1;i<n;i++){cin>>a[i];if((a[i].length()>max.length()) || (a[i].length()==max.length() && a[i]>max)){max=a[i];num=i+1;}}cout<<num<<endl;cout<<max<<endl;return 0;
}

P2676 [USACO07DEC] Bookshelf B

P2676 [USACO07DEC] Bookshelf B - 洛谷

貪心算法

先選最大的數（即最高的奶牛），一定能使取的數的數目（即奶牛數）最小

#include<bits/stdc++.h>
using namespace std;int main()
{long S[200005];long N,B,sum=0;cin>>N>>B;int num=0;for(int i=0;i<N;i++){cin>>S[i];}sort(S,S+N);for(int i=N-1;i>=0;i--){sum+=S[i];num++;if(sum>=B){break;}}cout<<num;return 0;
}

P1116 車廂重組

P1116 車廂重組 - 洛谷

計算每個數字后面有幾個數字比它小，再相加，就可以計算出需要的最少次數。

相對于冒泡排序

#include<bits/stdc++.h>
using namespace std;int main()
{int n;int a[10010];cin>>n;for(int i=0;i<n;i++){cin>>a[i];}int num=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(a[i]>a[j]){num++;}}}cout<<num;return 0;
}

P1068 [NOIP 2009 普及組] 分數線劃定

P1068 [NOIP 2009 普及組] 分數線劃定 - 洛谷

#include<bits/stdc++.h>
using namespace std;struct people
{int k;int s;
}per[5001];bool cmp(people a,people b)
{if(a.s!=b.s){return a.s>b.s;}else{return a.k<b.k;}
}int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>per[i].k>>per[i].s;}int num=m*1.5;sort(per,per+n,cmp);for(int i=num;i<n;i++){if(per[i].s==per[num-1].s){num++;}else{break;}}cout<<per[num-1].s<<" "<<num<<endl;for(int i=0;i<num;i++){cout<<per[i].k<<" "<<per[i].s<<endl;}return 0;
}

P5143 攀爬者

P5143 攀爬者 - 洛谷

#include<bits/stdc++.h>
using namespace std;struct zuobiao
{double x;double y;double z;
}dot[50001];bool cmp(zuobiao a,zuobiao b)
{return a.z<b.z;
}double solve(double x1,double x2,double y1,double y2,double z1,double z2)
{double x=pow(abs(x1-x2),2);double y=pow(abs(y1-y2),2);double z=pow(abs(z1-z2),2);double sum=pow(x+y+z,0.5);return sum;
}int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>dot[i].x>>dot[i].y>>dot[i].z;}sort(dot,dot+n,cmp);double ans=0.0;int tag=0;for(int i=1;i<n;i++){if(dot[i].z>dot[tag].z){ans+=solve(dot[tag].x,dot[i].x,dot[tag].y,dot[i].y,dot[tag].z,dot[i].z);tag=i;}else{continue;}}cout<<fixed<<setprecision(3)<<ans;return 0;
}

P1012 [NOIP 1998 提高組] 拼數

P1012 [NOIP 1998 提高組] 拼數 - 洛谷

to_string------>可以實現數字向字符串轉換（雖然這題沒用到）

兩個字符串?a,b，如果?a+b>b+a?則?a?排在前面。 這個公式的具體意思是當?a?排在?b?前面比?b?排在?a?前面要好，因為字典序更高，所以?a?自然要排在?b?的前面。

#include<bits/stdc++.h>
using namespace std;string a[25];bool cmp(string a,string b)
{return a+b>b+a;
}int main()
{int n,m;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n,cmp);for(int i=0;i<n;i++){cout<<a[i];}return 0;
}