day01:三大結構&數組&數組排序&查找(順序查找&二分查找)

三大結構:
順序結構：從上至下，從左至右的執行
分支結構：滿足flag為真就執行

if(flag){}

if(flag){}
else{}

if(flag){}
else if(flag){}
else if(flag){}
else{}

循環結構：滿足flag為真就一直執行

for(int i=0; i<n; i++){}
while(flag){}
do{}while(flag);

數組
數組是同類數據的一個集合，開辟的是一段連續的內存空間，
二維數組的下一行接著上一行的末尾。

初始化方式

int a[10];
int a[10]={0,1,2,3,4,5,6,7,8,9};
int a[10]={0,1,2,3};

const int N=10;
int a[N];

int類型，全局變量默認初始化為0，
局部變量如果未初始化，則初始化為隨機數，
局部變量如果部分初始化，則未初始化部分為0，

數組排序：

sort(a,a+n);//#include<algorithm>

sort(a, a+n); //sort(首地址,首地址+元素個數)

sort(a, a+n, cmp);//自定義比較函數，修改排序規則

sort() 默認升序排列，內部封裝快速排序方法，時間復雜度 nlogn

選擇排序
每一次選擇最小的元素放在未排序的最前面，時間復雜度：O(n^2)

for(int i=0; i<n-1; i++){//選擇排序
    for(int j=i+1; j<n; j++){
        if(a[i]>a[j]) {
            swap(a[i], a[j]);//交換 a[i],a[j]
        }
    }
}

歸并排序（暫作了解）：分治&歸并（作為最后的一個補充）

#include<bits/stdc++.h>
using namespace std;
/*
歸并排序：分治思想，先分小，再治小（排序），最后合并
在所有排序中，歸并排序最為穩定，時間復雜為 logn，也就是log2(n)
*/
int a[10]= {3,4,5,6,2,1,6,7,8,9};
int n=sizeof(a)/sizeof(int);   //通過數組大小計算元素個數
void merge(int arr[], int l, int mid, int r) {
    int i=l, j=mid+1, t=0, temp[r];//開一個臨時數組，存放答案
    while(i<=mid && j<=r) {
        if(arr[i]<=arr[j]) temp[t++] = arr[i++];
        else temp[t++] = arr[j++];
    }
    while(i<=mid)  temp[t++] = arr[i++];//處理剩余元素
    while(j<=r)    temp[t++] = arr[j++];
    t = 0;
    while(l<=r)	arr[l++] = temp[t++];//將答案賦給原數組
}
//int *arr 在這里等同于 int a[]，不過是使用指針的格式進行傳參
void MergeSort(int * arr,int l, int r) {
    if(l<r) {
        int mid = (l+r)/2;    //取中間作為分割點
        MergeSort(arr, l, mid);    //分左邊
        MergeSort(arr, mid+1, r);  //分右邊
        merge(arr, l, mid, r);     //左右合并
    }
}
int main() {
    MergeSort(a, 0, n-1);//自定義排序函數，MergeSort(數組首地址,排序起始下標,排序結束下標);
    for(int i=0; i<n; i++) {
        cout<<a[i]<<" ";
    }
    return 0;
}

數組是一段連續的內存空間，下標可以超過內存空間，且不會報錯，但是結果不對

二維數組的下一行與上一行的末尾是相鄰的

數組下標的靈活使用：int a[4][5];

00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34

ij: i表示行，j表示列，同行i不變，同列j不變 
左上角到右下角對角線：j-i是定值
左下角到右上角對角線：i+j是定值

查找(普通查找&二分查找)
普通查找其實就是暴力枚舉，直到找到目標
如：給你n個數據，存放在數組a[n]中，保證每個數不同，請找出某個數在該數組的位置

for(int i=0; i<n; i++){
    if(a[i]==x){
        //i即為所求
    }
}

二分查找是基于一個已經排好序的數列，在其中查找某個值
如：給你一個數列：int a[10]={0,1,2,3,4,5,6,7,8,9}; 快速查找x在數列中的位置

int a[10]= {0,1,2,3,4,5,6,7,8,9};
int l=0, r=sizeof(a)/sizeof(int)-1;
int x=3; //cin>>x;
while(l<=r){    //滿足左下標小于等于右下標的前提 
    int mid = (l+r)/2;
    if(a[mid]<x){//中間的數比x小，則x在右半部分 
        l = mid+1; 
    }else if(a[mid]>x){//中間的數比x大，則x在左半部分
        r=mid-1;
    } else{
        cout<<mid; break;//找到答案，輸出并退出循環 
    }
}

1.P3954 [NOIP2017 普及組] 成績

【題目描述】牛牛最近學習了C++入門課程，這門課程的總成績計算方法是：

總成績=作業成績×20%+小測成績×30%+期末考試成績×50%

牛牛想知道，這門課程自己最終能得到多少分。

輸入格式：
三個非負整數A,B,C，分別表示牛牛的作業成績、小測成績和期末考試成績。
相鄰兩個數之間用一個空格隔開，三項成績滿分都是100分。

輸出格式：一個整數，即牛牛這門課程的總成績，滿分也是100分。

輸入樣例：100 100 80

輸出樣例：90

題解：這就是一個順序結構，但是注意涉及到小數的要不要用double

#include<bits/stdc++.h>//萬能頭文件
using namespace std;
int main() {
    int a,b,c;    cin>>a>>b>>c;
    cout<<a*0.2+b*0.3+c*0.5;
    return 0;
}

2. P1085 [NOIP2004 普及組] 不高興的津津

【題目描述】津津上初中了。媽媽認為津津應該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各科復習班。另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興。假設津津不會因為其它事不高興，并且她的不高興不會持續到第二天。請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興。

輸入格式：
輸入包括7行數據，分別表示周一到周日的日程安排。
每行包括兩個小于10的非負整數，用空格隔開，
分別表示津津在學校上課的時間和媽媽安排她上課的時間。

輸出格式：一個數字。
如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用
1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周日）。
如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天。

輸入樣例：

輸出樣例：3

題解：就是求那天的和值最大，最大第一次出現的位置

#include<bits/stdc++.h>
using namespace std;
int main() {
    int max=0;    //最多上課時間
    int k=0;      //最不高興的那一天
    for(int i=1; i<=7; i++) {
        int a,b;    cin>>a>>b;
        if(a+b>max && a+b>8) {
            max = a+b;    k = i;
        }
    }
    cout<<k;    return 0;
}

3. P1046 [NOIP2005 普及組] 陶陶摘蘋果

【題目描述】陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結出 10 個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個 30 厘米高的板凳，當她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試。

現在已知 10 個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數目。假設她碰到蘋果，蘋果就會掉下來。

輸入格式：輸入包括兩行數據（（全部數據以厘米為單位））
第一行包含10個100到200之間（包括100和200）的整數分別表示10個蘋果到地面的高度，兩個相鄰的整數之間用一個空格隔開。
第二行只包括一個100到120之間（包含100和120）的整數，表示陶陶把手伸直的時候能夠達到的最大高度。

輸出格式：輸出一個整數，表示陶陶能夠摘到的蘋果的數目。

輸入樣例：

100 200 150 140 129 134 167 198 200 111
110

輸出樣例：5

題解：注意只要碰到就行，所以蘋果高度<= 能摸到的最大高度即可

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10];
    for(int i=0; i<10; i++) cin>>a[i];
    int h, ans=0; cin>>h;
    for(int i=0; i<10; i++){
        if(a[i]<=h+30){//注意要等于
            ans++;
        }
    }
    cout<<ans; return 0;
}

4. P1980 [NOIP2013 普及組] 計數問題

【題目描述】試計算在區間 1 到 n 的所有整數中，數字x（0 ≤ x ≤ 9）共出現了多少次？

例如，在 1到11中，即在1,2,3,4,5,6,7,8,9,10,11 中，數字 11 出現了 44 次。

輸入格式：2個整數n，x，之間用一個空格隔開。

輸出格式：1個整數，表示x出現的次數。

輸入樣例：11 1

輸出樣例：4

題解：對1到n，進行一次枚舉，同時判斷枚舉數據中的x個數

#include<bits/stdc++.h>
using namespace std;
int main(){ //n=1e6 = 1000000
    int n,x, ans=0; cin>>n>>x;
    for(int i=1; i<=n; i++){
        int temp=i; // 臨時變量
        while(temp!=0){
            if(temp%10==x) ans++; //如果個位數等于x，則答案+1
            temp /= 10;// temp = temp/10; 舍去個位數
        }
    }
    cout<<ans;    return 0;
}

5. P1035 [NOIP2002 普及組] 級數求和

【題目描述】已知：Sn= 1+1/2+1/3+…+1/n。顯然對于任意一個整數 k，當 n 足夠大的時候，Sn>k。

現給出一個整數 k，要求計算出一個最小的 n，使得 Sn>k。

輸入格式：一個正整數 k

輸出格式：一個正整數 n

輸入樣例：1

輸出樣例：2

題解：注意大坑：需要開double(小數后15位有效)，float(小數后7位有效)會出bug。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int k,n=0; cin>>k;
    double s=0;//注意double
    while(s<=k){
        ++n;    s += 1.0/n;//公式
    }
    cout<<n;    return 0;
}

6.P1008 [NOIP1998 普及組] 三連擊

【題目描述】將1,2,…,9 共 9 個數分成 3 組，分別組成 3個三位數，且使這3個三位數構成 1 : 2 : 3的比例，試求出所有滿足條件的3 個三位數。

輸入格式：無輸入

輸出格式：若干行，每行 3 個數字。按照每行第1 個數字升序排列。

輸入樣例：無

輸出樣例：

192 384 576
* * *
...

* * *（剩余部分不予展示）

題解：注意使用技巧 -- 打標記，如果數字 i 出現了，那么 t[i]=1,否則 t[i] =0;

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i=100; i<=333; i++){
        int a=i, b=2*i, c=3*i;
        int t[10]={0}, sum=0;//對1-9進行計數，出現過則為1,未出現則為0
        //memset(t, 0, sizeof(t)); //初始化為0
        t[a/100]=1, t[a/10%10]=1, t[a%10]=1; 
        t[b/100]=1, t[b/10%10]=1, t[b%10]=1; 
        t[c/100]=1, t[c/10%10]=1, t[c%10]=1; 
        for(int j=1; j<=9; j++) sum += t[j];
        if(sum==9) cout<<a<<" "<<b<<" "<<c<<endl;
    } return 0;
}

7. P1047 [NOIP2005 普及組] 校門外的樹

【題目描述】某校大門外長度為 l 的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是 1 米。我們可以把馬路看成一個數軸，馬路的一端在數軸 0 的位置，另一端在 l 的位置；數軸上的每個整數點，即 0，1,2,3，...， l 都種有一棵樹。

由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。

輸入格式：第一行有兩個整數，分別表示馬路的長度 l 和區域的數目 m。

接下來 m 行，每行兩個整數 u, v，表示一個區域的起始點和終止點的坐標。

輸出格式：輸出一行一個整數，表示將這些樹都移走后，馬路上剩余的樹木數量。

輸入樣例：

輸出樣例：298

題解：也是一個打標記的小技巧

#include<bits/stdc++.h>
using namespace std;
const int N=1e4;
int a[N];//0表示有樹，1表示無樹
int main(){
    int l,m; cin>>l>>m;
    for(int i=1; i<=m; i++){
        int u,v; cin>>u>>v;
        for(int j=u; j<=v; j++) a[j]=1;//樹被移栽了
    }
    int ans=0;
    for(int i=0; i<=l; i++)
        if(a[i]==0) ans++;//樹木個數+1
    cout<<ans;    return 0;
}

8. P1059 [NOIP2006 普及組] 明明的隨機數

【題目描述】明明想在學校中請一些同學一起做一項問卷調查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(N≤100)，對于其中重復的數字，只保留一個，把其余相同的數去掉，不同的數對應著不同的學生的學號。然后再把這些數從小到大排序，按照排好的順序去找同學做調查。請你協助明明完成“去重”與“排序”的工作。

輸入格式：

輸入有兩行，第1行為1個正整數，表示所生成的隨機數的個數N
第2行有N個用空格隔開的正整數，為所產生的隨機數。

輸出格式：

輸出也是兩行，第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;
const int N=1e4;
int a[N], b[N], cnt=0;
int main(){//解法1 - 桶排序的思想
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        int x; cin>>x;
        a[x]=1;
    }
    for(int i=1; i<=1000; i++){
        if(a[i]==1) b[++cnt]=i;
    }
    cout<<cnt<<endl;
    for(int i=1; i<=cnt; i++)     cout<<b[i]<<" ";
    return 0;
}

int main_ac(){//解法2 - 模擬一遍，先排序，再去重
    int n; cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n);//升序排序
    b[0]=a[0];
    for(int i=0; i<n-1; i++){
        if(b[cnt]!=a[i+1]){
            b[++cnt] = a[i+1];
        }
    }
    cout<<cnt+1<<endl;
    for(int i=0; i<=cnt; i++)    cout<<b[i]<<' ';
    return 0;
}

9.P2669 [NOIP2015 普及組] 金幣

【題目描述】國王將金幣作為工資，發放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣……；這種工資發放模式會一直這樣延續下去：當連續 n天每天收到 n枚金幣后，騎士會在之后的連續 n+1天里，每天收到 n+1 枚金幣。

請計算在前 k天里，騎士一共獲得了多少金幣。

輸入格式：一個正整數 k，表示發放金幣的天數。

輸出格式：一個正整數，即騎士收到的金幣數。

輸入樣例：6

輸出樣例：14

題解：主要是將題目信息歸納出來，學會如何歸納總結，養成用數據表達題意的習慣。

/* 根據題目可列出下表，找到規律
1
2 2
3 3 3
4 4 4 4
....*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    int k,sum=0; cin>>k;
    int i=1;
    while(k>0){
        for(int j=1; j<=i && k>0; j++){
            sum += i;    k--;
        }
        i++;
    }
    cout<<sum;    return 0;
}

推薦：P1014 [NOIP1999 普及組] Cantor 表這道題目也是同樣類型的題目，只是分了左右兩個方向

10.P1909 [NOIP2016 普及組] 買鉛筆

【題目描述】P老師需要去商店買n支鉛筆作為小朋友們參加NOIP的禮物。她發現商店一共有 33種包裝的鉛筆，不同包裝內的鉛筆數量有可能不同，價格也有可能不同。為了公平起見，P老師決定只買同一種包裝的鉛筆。

商店不允許將鉛筆的包裝拆開，因此P老師可能需要購買超過n支鉛筆才夠給小朋友們發禮物。現在P老師想知道，在商店每種包裝的數量都足夠的情況下，要買夠至少n支鉛筆最少需要花費多少錢。

輸入格式：
第一行包含一個正整數n，表示需要的鉛筆數量。
接下來三行，每行用2個正整數描述一種包裝的鉛筆：
其中第1個整數表示這種包裝內鉛筆的數量，第2個整數表示這種包裝的價格。
保證所有的7個數都是不超過10000的正整數。

輸出格式：1個整數，表示P老師最少需要花費的錢。

輸入樣例：

輸出樣例：54

題解：題目要求用最少的錢達到目的即可，所以先設money極大，依次取當前方案的最小值即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, money=1e8; cin>>n;
    for(int i=1; i<=3; i++){
        int num, price; cin>>num>>price;
        if(money>ceil(1.0*n/num)*price)//最便宜
            money=ceil(1.0*n/num)*price;
    }
    cout<<money;    return 0;
}

11. P1014 [NOIP1999 普及組] Cantor 表

【題目描述】

現代數學的著名證明之一是 Georg Cantor 證明了有理數是可枚舉的。他是用下面這一張表來證明這一命題的：

1/1, 1/2, 1/3, 1/4, 1/5, …
2/1, 2/2, 2/3, 2/4, …
3/1, 3/2, 3/3, …
4/1, 4/2, …
5/1, …
…

我們以 Z 字形給上表的每一項編號。第一項是 1/1，然后是1/2，2/1，3/1，2/2，…

輸入格式：整數N（1≤N≤107）。

輸出格式：表中的第 N項。

輸入樣例：7

輸出樣例：1/4

題解：本題屬于找規律的題目，要學會用數據來展示規律

#include<bits/stdc++.h>
using namespace std;
/* 找規律：
1/1
2/1    1/2
3/1    2/2    1/3
4/1    3/2    2/3    1/4
5/1    4/2    3/3    2/4    1/5
確定第n個數所在行列：i,j 
奇數行：左往右數
偶數行：右往左數
并且：x+y=i+1     */
int main() {
    int i=0,j=0,sum=0,x=1,y=1;
    int n;    cin>>n;
    while(sum<n){
        i++;
        sum += i;
    }
    j = sum-n+1;
    if(i%2!=0)  x=j, y=i+1-x;//奇數，左往右數
    else  x=i-j+1, y=i+1-x; //偶數，右往左數
    cout<<x<<"/"<<y<<endl;    return 0;
}

posted @ 2021-08-01 07:14 HelloHeBin 閱讀(327) 評論(0) 收藏舉報

刷新頁面返回頂部

HelloHeBin

在醒著的時間里，追求你認為最有意義的~

day01:三大結構&數組&數組排序&查找(順序查找&二分查找)