新手入門刷題（專題二）排序
4.12
宇宙總統
題目描述
地球曆公元 6036 年，全宇宙準備競選一個最賢能的人當總統，共有 n個非凡拔尖的人競選總統，現在票數已經統計完畢，請你算出誰能夠當上總統。
輸入樣例
5 //參賽人數
98765 //得票數 票數可能會很大，可能會到 100位數字。
12365
87954
1022356
985678
輸出樣例
4
1022356
思路
本題的票數用string存儲，比較時先比較票長，長度一緻則比較大小。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct Candidate {
int num;//序号
string grade;//票數
} pre[25];
//自定義比較函數
bool cmp(Candidate a,Candidate b){
if(a.grade.length()>b.grade.length()) return a.grade.length()>b.grade.length();
else if(a.grade.length()==b.grade.length()) return a.grade>b.grade;
return false;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>pre[i].grade;
pre[i].num = i;
}
sort(pre+1,pre+n+1,cmp);
cout<<pre[1].num<<endl<<pre[1].grade;
return 0;
}
[USACO07DEC]Bookshelf B
題目描述
略，求最少幾個奶牛即可到書架高度
輸入樣例
6 40 //奶牛數為6，書架高為40
6 //第一個奶牛高度
18
11
13
19
11
輸出樣例
3
思路
先快排所有奶牛高度，再從大到小相加，直到>=書架高度，統計相加的奶牛個數
代碼
#include <iostream>
#include<algorithm>
using namespace std;
int n,b,h[20020],t,k;
//快排模闆要記住
int qs(int q[],int l,int r){
if(l>=r) return q[l];
int i = l-1,j = r+1, x = q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
qs(q, l, j);
qs(q, j + 1, r);
}
int main() {
cin>>n>>b;
for(int i=0;i<n;i++) cin>>h[i];
qs(h,0,n-1);
while(t<b&&k<n){
t += h[n-1-k];
k++;
}
cout<<k;
return 0;
}
車廂重組
題目描述
好家夥，考查冒泡可還行。
代碼
#include <iostream>
#include<algorithm>
using namespace std;
int n,t[10010],times;
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(t[i]>t[j]) {
swap(t[i],t[j]);
times++;
}
}
}
printf("%d",times);
return 0;
}
歡樂的跳
題目描述
一個包含n個元素的整數數組，如果數組兩個連續元素之間差的絕對值包括了[1,n-1]之間的所有整數，則稱之符合“歡樂的跳”，如數組 {1，4，2，3} 符合“歡樂的跳”，因為差的絕對值分别為：3,2,1。
給定一個數組，你的任務是判斷該數組是否符合“歡樂的跳”。
輸入樣例
5 1 4 2 -1 6 //第一個數字代表數組長度，之後代表每一個數字
輸出樣例
jolly //符合“歡樂的跳”輸出
Not jolly //不符合“歡樂的跳”輸出
思路
數組長度 n ( 1 ≤ n ≤ 1000 )
數組中的數字範圍 [-100000000，100000000]
本題提供兩種解法
第一種用桶裝兩數之差，即采用數組下标的方式存儲兩數之差，不過數組的長度要大于100000000。
隻需要數組範圍 [1,n-1] 之内的數全是 1 即符合“歡樂的跳”，具體見代碼一。
第二種方法，我們可以研究一下題目，顯然在存數組的過程中即可計算兩數之差，一旦兩數之差出現重複，一定不符合“歡樂的跳”，具體見代碼二。
代碼一
#include <iostream>
#include<algorithm>
using namespace std;
int n,t[1010],num[200000000];
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
}
//桶
for(int i=0;i<n-1;i++){
int tmp;
tmp = t[i]>=t[i+1]?t[i]-t[i+1]:t[i+1]-t[i];
num[tmp]++;
}
for(int i=1;i<n;i++){
if(num[i]==0){
printf("Not jolly");
return 0;
}
}
printf("Jolly");
return 0;
}
代碼二
#include <iostream>
using namespace std;
int n,a,b,c;
bool d[1010];
int main() {
//輸入數組長度
scanf("%d",&n);
//輸入第一個數
scanf("%d",&a);
//從第二個數開始輸入
for(int i=1;i<n;i++){
scanf("%d",&b);
//計算兩數之差
c = a>=b?a-b:b-a;
//兩數之差不在[1,n-1]之内，必定不符合
if(c>=1&&c<=n-1){
//判斷是否重複，重複也必定不符合
if(d[c]) {
printf("Not jolly");
return 0;
}
//不重複，則繼續
else d[c] = true;
}else {
printf("Not jolly");
return 0;
}
//指派第二個數給第一個數，開啟下輪循環
a = b;
}
//能夠完成輸入循環，則必定符合
printf("Jolly");
return 0;
}
4.13
[NOIP2009 普及組] 分數線劃定
題目描述
世博會志願者的選拔工作正在 A 市如火如荼的進行。為了選拔最合适的人才，A市對所有報名的選手進行了筆試，筆試分數達到面試分數線的選手方可進入面試。面試分數線根據計劃錄取人數的 150% 劃定，即如果計劃錄取m名志願者，則面試分數線為排名第 m×150%（向下取整）名的選手的分數，而最終進入面試的選手為筆試成績不低于面試分數線的所有選手。
現在就請你編寫程式劃定面試分數線，并輸出所有進入面試的選手的報名号和筆試成績。
輸入樣例
6 3 //報名參加筆試的選手總數 計劃錄取的志願者人數
1000 90 //選手的報名号 選手的筆試成績
3239 88
2390 95
7231 84
1005 95
1001 88
輸出樣例
88 5
1005 95
2390 95
1000 90
1001 88
3239 88
//按照筆試成績從高到低輸出，如果成績相同，則按報名号由小到大的順序輸出。
說明/提示
【樣例說明】
m×150%=3×150%=4.5，向下取整後為4。保證4個人進入面試的分數線為88，但因為88有重分，是以所有成績大于等于88 的選手都可以進入面試，故最終有5個人進入面試。
思路
學習新排序啦, 歸并排序, 時間複雜度nlogn, 穩定!!!
快排時間複雜度為nlogn, 但是不穩定, 本題如果成績相同時按輸入先後順序輸出, 則使用快排不合适, 因為不穩定會導緻成績相同但是輸出順序與輸入順序不一緻.
但是本題要求根據 成績從大到小 和 成績相同則根據編号從小到大輸出, 是以使用 快排 和 歸并排序 皆可
歸并排序模闆
const int N=1e6+10;
int q[N],temp[N];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
//正序
if (q[i] <= q[j]) tmp[k++] = q[i++];
//逆序
//if (q[i] >= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
采用歸并排序解題代碼
#include<iostream>
using namespace std;
struct Emp{
int num;
int grade;
}emp[5050],tmp[5050];
int n,m;
//根據歸并排序模闆修改，穩定
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
//成績從大到小
if (emp[i].grade > emp[j].grade) tmp[k++] = emp[i++];
//成績相同,編号從小到大
else if (emp[i].grade == emp[j].grade && emp[i].num <= emp[j].num) tmp[k++] = emp[i++];
else tmp[k++] = emp[j++];
while (i <= mid) tmp[k++] = emp[i++];
while (j <= r) tmp[k++] = emp[j++];
for (int i = l, j = 0; i <= r; i++, j++) emp[i] = tmp[j];
}
int main(){
scanf("%d%d",&n,&m);
m = m * 1.5;
for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
merge_sort(1,n);
//成績相同時接着往下找
while(emp[m].grade==emp[++m].grade);
printf("%d %d\n",emp[m].grade,--m);
for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
return 0;
}
采用快排解題代碼
#include<iostream>
using namespace std;
struct Emp{
int num;
int grade;
}emp[5050];
int n,m;
//改寫快排
void qs(int l,int r){
if(l>=r) return;
int i = l-1, j = r+1, x = emp[(r+l)>>1].grade, y = emp[(r+l)>>1].num;
while(i<j){
//成績從大到小 成績相同,編号從小到大
do i++;while(emp[i].grade>x||(emp[i].grade==x&&emp[i].num<y));
do j--;while(emp[j].grade<x||(emp[j].grade==x&&emp[j].num>y));
if(i<j) swap(emp[i],emp[j]);
}
qs(l,j);
qs(j+1,r);
}
int main(){
scanf("%d%d",&n,&m);
m = m * 1.5;
for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
qs(1,n);
//成績相同時接着往下找
while(emp[m].grade==emp[++m].grade);
printf("%d %d\n",emp[m].grade,--m);
for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
return 0;
}
攀爬者
題目描述
HKE考完GDOI之後跟他的神犇小夥伴們一起去爬山。
他在地形圖上标記了N個點，每個點Pi都有一個坐标(xi,yi,zi)。所有點對中，高度值z不會相等。HKE準備從最低的點爬到最高的點，他的攀爬滿足以下條件：
(1) 經過他标記的每一個點；
(2) 從第二個點開始，他經過的每一個點高度z都比上一個點高；
(3) HKE會飛，他從一個點Pi爬到Pj的距離為兩個點的歐幾裡得距離。即，
( X i − X j ) 2 + ( Y i − Y j ) 2 + ( Z i − Z j ) 2 \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2} (Xi−Xj)2+(Yi−Yj)2+(Zi−Zj)2
現在，HKE希望你能求出他攀爬的總距離。
輸入樣例
5 //點的個數
2 2 2 //x y z
1 1 1
4 4 4
3 3 3
5 5 5
輸出樣例
6.928
說明/提示
【樣例說明】
對于100%的資料，1≤N≤50000，答案的範圍在double範圍内。
思路
先按照z軸排序, 再計算兩點距離.
代碼
#include<iostream>
#include<math.h>
#include<cmath>
#include<algorithm>
using namespace std;
double ans;
struct Node {
int x,y,z;
//重載<
bool operator < (const Node &b)const{
return z<b.z;
}
} a[50050];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a,a+n);
for(int i=1;i<n;i++) ans+=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",ans);
return 0;
}
4.14
生日
題目描述
cjf
君想調查學校 OI 組每個同學的生日，并按照年齡從大到小的順序排序，如果有兩個同學生日相同,輸入靠後的同學先輸出。但
cjf
君最近作業很多，沒有時間，是以請你幫她排序。
輸入樣例
3 //人數
Yangchu 1992 4 23 //姓名 生日
Qiujingya 1993 10 13
Luowen 1991 8 1
輸出樣例
Luowen //姓名
Yangchu
Qiujingya
說明/提示
資料規模
1<n<100
length(s)<20
思路
結構體加sort函數，本題和上一題基本一樣。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
struct Students {
int nu;
char na[25];
int ye;
int mo;
int da;
//sort預設從小到大排序，我們需要重載 < 運算符号
//重載<
bool operator < (const Students &b)const{
if(ye<b.ye) return ye<b.ye;
else if(ye==b.ye&&mo<b.mo) return mo<b.mo;
else if(ye==b.ye&&mo==b.mo&&da<b.da) return da<b.da;
else if(ye==b.ye&&mo==b.mo&&da==b.da&&nu>b.nu) return nu>b.nu;
return false;
}
} a[110];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
a[i].nu = i;
//提供兩種輸入方法
//小知識,字元串名稱本身就是位址，無需添加位址符
// scanf("%s %d %d %d",a[i].na,&a[i].ye,&a[i].mo,&a[i].da);
cin>>a[i].na>>a[i].ye>>a[i].mo>>a[i].da;
}
sort(a,a+n);
for(int i=0;i<n;i++) printf("%s\n",a[i].na);
return 0;
}
[NOIP1998 提高組] 拼數
題目描述
設有 n個正整數 a1…an，将它們聯接成一排，相鄰數字首尾相接，組成一個最大的整數。
輸入樣例
4
7 13 4 246
輸出樣例
7424613
說明/提示
對于全部的測試點，保證
1 ≤ n ≤ 20 1≤n≤20 1≤n≤20
1 ≤ a i ≤ 1 0 9 1≤ai≤10^9 1≤ai≤109
思路
隻需要判段兩數先後相加的大小即可。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
string s[25];
//
bool cmp(string a,string b){
return a+b>b+a;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>s[i];
sort(s,s+n,cmp);
for(int i=0;i<n;i++) cout<<s[i];
return 0;
}
![Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)