2021-01-22總結
今天在家沒事，下午用了不到三個小時把之前缺課落下的第二章—資料排序的題給做完了，
這九道題總體來說做的還是挺順利的，除了第九題一開始忘記把橫坐標減掉 i 之后再排一遍順序，導致樣例雖然過了，但是提交 luogu WA 了三個點，其他題做得還不錯，就相當于復習了一遍各種排序方法（其實我就用到了sort，桶排和冒泡排序），
1、明明的亂數（Noip2006）
【問題描述】
明明想在學校中請一些同學一起做一項問卷調查，為了實驗的客觀性，他先用計算機生成了N個1到
1000 之間的隨機整數（N≤100），對于其中重復的數字，只保留一個，把其余相同的數去掉，不同的數對
應著不同的學生的學號，然后再把這些數從小到大排序，按照排好的順序去找同學做調查，請你協助明明
完成“去重”與“排序”的作業，
【輸入檔案】
輸入檔案 random.in 有 2 行，
第 1 行為 1 個正整數，表示所生成的亂數的個數：N
第 2 行有 N 個用空格隔開的正整數，為所產生的亂數，
【輸出檔案】
輸出檔案 random.out 也是 2 行，第 1 行為 1 個正整數 M，表示不相同的亂數的個數，第 2 行為 M 個
用空格隔開的正整數，為從小到大排好序的不相同的亂數，
【輸入樣例】
10
20 40 32 67 40 20 89 300 400 15
【輸出樣例】
8
15 20 32 40 67 89 300 400
#include<bits/stdc++.h>
using namespace std;
int n,a[1005],b[105],sum,q=1;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%d",&k);
a[k]++;
}
for(int i=1;i<=1005;i++){
if(a[i]!=0){
sum++;
b[q]=i;
q++;
}
}
printf("%d\n",sum);
for(int i=1;i<=q-1;i++){
printf("%d ",b[i]);
}
return 0;
}
/*
10
20 40 32 67 40 20 89 300 400 15
*/
2、車廂重組（carry）
【問題描述】
在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉，一個車站的職工發現橋的
長度最多能容納兩節車廂，如果將橋旋轉 180 度，則可以把相鄰兩節車廂的位置交換，用這種方法可以重
新排列車廂的順序，于是他就負責用這座橋將進站的車廂按車廂號從小到大排列，他退休后，火車站決定
將這一作業自動化，其中一項重要的作業是編一個程式，輸入初始的車廂順序，計算最少用多少步就能將
車廂排序，
【輸入檔案】
輸入檔案有兩行資料，第一行是車廂總數 N（不大于 10000），第二行是 N 個不同的數表示初始的車廂
順序，
【輸出檔案】
一個資料，是最少的旋轉次數，
【輸入樣例】
4
4 3 2 1
【輸出樣例】
6
#include<bits/stdc++.h>
using namespace std;
int n,a[10001],step;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n-1;i++){
for(int j=1;j<=n-1;j++){
if(a[j]>a[j+1]){
++step;
int mid=a[j];
a[j]=a[j+1];
a[j+1]=mid;
}
}
}
printf("%d",step);
return 0;
}
/*
4
4 3 2 1
*/
3、眾數(masses)
【問題描述】
由檔案給出N個1到 30000 間無序數正整數，其中 1≤N≤10000，同一個正整數可能會出現多次，出
現次數最多的整數稱為眾數，求出它的眾數及它出現的次數，
【輸入格式】
輸入檔案第一行是正整數的個數 N，第二行開始為 N 個正整數，
【輸出格式】
輸出檔案有若干行，每行兩個數，第 1 個是眾數，第 2 個是眾數出現的次數，
【輸入樣例】
12
2 4 2 3 2 5 3 7 2 3 4 3
【輸出樣例】
2 4
3 4
#include<bits/stdc++.h>
using namespace std;
int maxn,sum[101],n,a[30001];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%d",&k);
a[k]++;
}
for(int i=1;i<=30001;i++){
if(maxn<a[i]){
maxn=a[i];
}
}
int q=1;
for(int i=1;i<=30001;i++){
if(a[i]==maxn){
sum[q]=i;
q++;
}
}
for(int i=1;i<=q-1;i++){
printf("%d %d\n",sum[i],maxn);
}
return 0;
}
/*
12
2 4 2 3 2 5 3 7 2 3 4 3
*/
4、第 k 小整數(knumber)
【問題描述】
現有 n 個正整數，n≤10000，要求出這 n 個正整數中的第 k 個最小整數（相同大小的整數只計算一次），
k≤1000，正整數均小于 30000，
【輸入格式】
第一行為 n 和 k，第二行開始為 n 個正整數的值，整數間用空格隔開，
【輸出格式】
第 k 個最小整數的值；若無解，則輸出“NO RESULT”，
【輸入樣例】
10 3
1 3 3 7 2 5 1 2 4 6
【輸出樣例】
3
#include<bits/stdc++.h>
using namespace std;
int n,k,b[30005],sum;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
b[a]++;
}
for(int i=1;i<=30000;i++){
if(b[i]>=1){
sum++;
}
if(sum==k){
printf("%d",i);
return 0;
}
}
printf("NO RESULT");
return 0;
}
/*
10 3
1 3 3 7 2 5 1 2 4 6
*/
5、軍事機密(secret)
【問題描述】
軍方截獲的資訊由 n（n<=30000）個數字組成，因為是敵國的高端秘密，所以一時不能破獲，最原始
的想法就是對這 n 個數進行從小到大排序，每個數都對應一個序號，然后對第 i 個是什么數感興趣，現在
要求編程完成，
【輸入格式】
第一行 n，接著是 n 個截獲的數字，接著一行是數字 k，接著是 k 行要輸出數的序號，
【輸出格式】
k 行序號對應的數字，
【輸入樣例】
5
121 1 126 123 7
3
2
4
3
【輸出樣例】
7
123
121
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,a[30005],b[30005];
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",&b[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=k;i++){
printf("%d\n",a[b[i]]);
}
return 0;
}
/*
5
121 1 126 123 7
3
2
4
3
*/
6、獎學金(Noip2007)
【問題描述】
某小學最近得到了一筆贊助，打算拿出其中一部分為學習成績優秀的前 5 名學生發獎學金，期末，每
個學生都有 3 門課的成績：語文、數學、英語，先按總分從高到低排序，如果兩個同學總分相同，再按語
文成績從高到低排序，如果兩個同學總分和語文成績都相同，那么規定學號小的同學排在前面，這樣，每
個學生的排序是唯一確定的，
任務：先根據輸入的 3 門課的成績計算總分，然后按上述規則排序，最后按排名順序輸出前 5 名學生
的學號和總分，注意，在前 5 名同學中，每個人的獎學金都不相同，因此，你必須嚴格按上述規則排序，
例如，在某個正確答案中，如果前兩行的輸出資料（每行輸出兩個數：學號、總分）是：
7 279
5 279
這兩行資料的含義是：總分最高的兩個同學的學號依次是 7 號、5 號，這兩名同學的總分都是 279（總
分等于輸入的語文、數學、英語三科成績之和），但學號為 7 的學生語文成績更高一些，如果你的前兩名的
輸出資料是：5 279
7 279
則按輸出錯誤處理，不能得分，
【輸入格式】
輸入檔案 scholar.in 包含 n+1 行：
第 1 行為一個正整數 n，表示該校參加評選的學生人數，
第2到 n+1 行，每行有 3 個用空格隔開的數字，每個數字都在 0 到 100 之間，第 j 行的 3 個數字依次
表示學號為 j-1 的學生的語文、數學、英語的成績，每個學生的學號按照輸入順序編號為 1~n（恰好是輸
入資料的行號減 1）， 所給的資料都是正確的，不必檢驗，
【輸出格式】
輸出檔案 scholar.out 共有 5 行，每行是兩個用空格隔開的正整數, 依次表示前 5 名學生的學號和總
分，
【輸入輸出樣例 1】
scholar.in scholar.out
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
6 265
4 264
3 258
2 244
1 237
【輸入輸出樣例 2】
scholar.in scholar.out
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
8 265
2 264
6 264
1 258
5 258
【限制】
50%的資料滿足：各學生的總成績各不相同
100%的資料滿足：6<=n<=300
#include<bits/stdc++.h>
using namespace std;
int n;
struct cwy{
int id,ch,ma,en,tot;
}a[305];
bool cmp(cwy x,cwy y){
if(x.tot!=y.tot)
return x.tot>y.tot;
else{
if(x.ch!=y.ch)
return x.ch>y.ch;
else{
return x.id<y.id;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].ch,&a[i].ma,&a[i].en);
a[i].tot=a[i].ch+a[i].ma+a[i].en;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=5;i++){
printf("%d %d\n",a[i].id,a[i].tot);
}
return 0;
}
/*
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
*/
7、統計數字(Noip2007)
【問題描述】
某次科研調查時得到了n個自然數，每個數均不超過 1500000000（1.5109
），已知不相同的數不超過
10000 個，現在需要統計這些自然數各自出現的次數，并按照自然數從小到大的順序輸出統計結果，
【輸入格式】
輸入檔案 count.in 包含 n+1 行：
第 1 行是整數 n，表示自然數的個數，
第 2~n+1 行每行一個自然數，
【輸出格式】
輸出檔案 count.out 包含 m 行（m 為 n 個自然數中不相同數的個數），按照自然數從小到大的順序輸出，
每行輸出兩個整數，分別是自然數和該數出現的次數，其間用一個空格隔開，
【輸入輸出樣例】
count.in count.out
8
2
4
2
4
5
100
2
100
2 3
4 2
5 1
100 2
【限制】
40%的資料滿足：1<=n<=1000
80%的資料滿足：1<=n<=50000
100%的資料滿足：1<=n<=200000，每個數均不超過 1 500 000 000（1.5109
）
#include<bits/stdc++.h>
using namespace std;
long long p=1,n;
struct cwy{
long long num,times;
}a[20001];
bool cmp(cwy x,cwy y){
return x.num<y.num;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++){
int k,flag=0;
scanf("%lld",&k);
for(int i=1;i<=p-1;i++){
if(a[i].num==k){
flag=1;
a[i].times++;
break;
}
}
if(flag==0){
a[p].num=k;
a[p].times++;
p++;
}
}
sort(a+1,a+p,cmp);
for(int i=1;i<=p-1;i++){
printf("%lld %lld\n",a[i].num,a[i].times);
}
return 0;
}
/*
8
2
4
2
4
5
100
2
100
*/
8、輸油管道問題(pipe)
【問題描述】
某石油公司計劃建造一條由東向西的主輸油管道，該管道要穿過一個有n 口油井的油田，從每口油井
都要有一條輸油管道沿最短路徑(或南或北)與主管道相連，如果給定n口油井的位置，即它們的x 坐標（東
西向）和y 坐標（南北向），應如何確定主管道的最優位置，即使各油井到主管道之間的輸油管道長度總
和最小的位置？證明可在規定時間內確定主管道的最優位置，
【編程任務】
給定n 口油井的位置,編程計算各油井到主管道之間的輸油管道最小長度總和，
【輸入格式】
第1 行是油井數n，1≤n≤10000，接下來n 行是油井的位置，每行2個整數x和y，-10000≤x,y≤10000，
【輸出格式】
第1 行中的數是油井到主管道之間的輸油管道最小長度總和，
【輸入樣例】
5
1 2
2 2
1 3
3 -2
3 3
【輸出樣例】
6
#include<bits/stdc++.h>
using namespace std;
int n,x[10005],y[10005],ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
sort(y+1,y+n+1);
for(int i=1;i<=n/2;i++){
ans+=y[n-i+1]-y[i];
}
printf("%d",ans);
return 0;
}
/*
5
1 2
2 2
1 3
3 -2
3 3
*/
9、士兵站隊問題
【問題描述】
在一個劃分成網格的操場上，n個士兵散亂地站在網格點上，網格點由整數坐標(x,y)表示，士兵們可
以沿網格邊上、下、左、右移動一步，但在同一時刻任一網格點上只能有一名士兵，按照軍官的命令，士
兵們要整齊地列成一個水平佇列，即排列成(x,y),(x+1,y),…,(x+n-1,y)，如何選擇x 和y的值才能使士兵
們以最少的總移動步數排成一列，
【編程任務】
計算使所有士兵排成一行需要的最少移動步數，
【輸入格式】
第1 行是士兵數n，1≤n≤10000，接下來n 行是士兵的初始位置，每行2 個整數x 和y，-10000≤x，
y≤10000，
【輸出格式】
第1 行中的數是士兵排成一行需要的最少移動步數，
【輸入樣例】
5
1 2
2 2
1 3
3 -2
3 3
【輸出樣例】
8
#include<bits/stdc++.h>
using namespace std;
int n,x[10005],y[10005],ans1,ans2,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
sort(y+1,y+n+1);
for(int i=1;i<=n;i++){
ans1+=abs(y[(n+1)/2]-y[i]);
}
sort(x+1,x+n+1);
for(int i=1;i<=n;i++){
x[i+1]-=i;
}
sort(x+1,x+n+1);
for(int i=1;i<=n;i++){
ans2+=abs(x[(n+1)/2]-x[i]);
}
ans=ans1+ans2;
printf("%d",ans);
return 0;
}
/*
5
1 2
2 2
1 3
3 -2
3 3
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251764.html
標籤：其他
上一篇：洗掉WIN10右鍵解壓縮選單
下一篇：資料結構型別（記憶體篇）