思想：總是做出在當前看來是最好的選擇

例題一、排隊打水問題

n個人，r個水龍頭，花費時間最少的安排？（包含等待時間）

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){int n,r,s=0;cin>>n>>r;int a[510]={0};for (int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);//將數組a[]從小到大排序，需要用頭文件#include <bits/stdc++.h>/*for (int i=1;i<=n;i++){cout<<a[i]<<" ";}*///輸出：2 4 6 5for(int i=1;i<=n;i++){if(i>=r+1)a[i]=a[i]+a[i-r];s+=a[i];}cout<<s;return 0;
}

例題二、分發餅干（LeetCode455）

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子?i，都有一個胃口值?g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干?j，都有一個尺寸?s[j]?。如果?s[j]?>= g[i]，我們可以將這個餅干?j?分配給孩子?i?，這個孩子會得到滿足。你的目標是滿足盡可能多的孩子，并輸出這個最大數值。

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){int g[500]={0};			//孩子int s[500]={0};			//餅干int i,j,n=0;				//n是滿足的個數cin>>i>>j;for(int k=0;k<=i-1;k++)cin>>g[k];for(int k=0;k<=j-1;k++)cin>>s[k];sort(s,s+j);sort(g,g+i);int index=j-1;for(int k=i-1;k>=0;k--){if(index>=0&&s[index]>=g[k]){n++;index--;}}cout<<n;return 0;
}
/*
輸入1：
2 3
1 2
1 2 3
輸出1：
2輸入2：
4 4
1 2 7 10
1 3 5 9
輸出2：
3
*/

例題三、最大子數組和

53. 最大子數組和

給你一個整數數組?nums?，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組是數組中的一個連續部分。

#include<iostream>
using namespace std;
int main(){int n=0,result=0,count=0;int a[500]={0};int j=0;do{cin>>a[j];j++;}while(getchar()!='\n');n=j;for(int i=0;i<=n;i++){count+=a[i];if(count>result)result=count;if(count<0)count=0;}cout<<result<<endl;return 0;
}

例題四、買賣股票的最佳時機 II

122. 買賣股票的最佳時機 II - 力扣（LeetCode）

#include<iostream>
using namespace std;
int main(){int n=0,sum=0;int a[500]={0};int j=0;do{cin>>a[j];j++;}while(getchar()!='\n');n=j;for(int i=1;i<=n;i++){sum+=max(a[i]-a[i-1],0);}cout<<sum<<endl;return 0;
}
/*
輸入：7 1 5 10 3 6 4
輸出：12
*/

例題五、跳躍問題I

55. 跳躍游戲 - 力扣（LeetCode）

思路：看cover面積是否超過即可！

#include<iostream>
#include<cstdio>
using namespace std;
int main(){int n,result=0,count;cin>>n;int a[500]={0};for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<=n;i++){count+=a[i];if(count>result)result=count;if(count<0)count=0;}cout<<result<<endl;return 0;
}

例題六、跳躍問題II

45. 跳躍游戲 II - 力扣（LeetCode）

#include<iostream>
#include<cstdio>
#include <bits/stdc++.h>
using namespace std;
int main(){int result=0,next=0,cur=0;int num[10001]={0};int i=0;do{cin>>num[i];i++;}while(getchar()!='\n');int j;j=i;for(i=0;i<=j;i++){next = max(next,i+num[i]);if(i==cur){result++;cur=next;if(next>=j-1)break;}}cout<<result<<endl;return 0;
}

例題七、K次取反后最大化的數組和

1005. K 次取反后最大化的數組和 - 力扣（LeetCode）

#include<iostream>
#include<cstdio>
#include <bits/stdc++.h>
using namespace std;
int main(){int a[10001];int K,i=0;do{cin>>a[i];i++;}while(getchar()!='\n');int j=i;//j是數組元素個數cin>>K;sort(a,a+j);//將所有數從小到大排列int negative=0;//記錄負數的個數for(i=0;i<=j-1;i++){if(a[i]<0)negative++;}if(K<=negative){//反轉次數小于負數個數，則將負數從最小開始反轉for(i=0;i<=K-1;i++)a[i]=-a[i];}if(K>=negative){//反轉次數大于負數個數，則將所有負數反轉//再將數組重排，反轉最小非負數即可//（剩余次數為偶數不需改變，為奇數將a[0]反轉即可！int x=0;while(a[x]<0){a[x]=-a[x];x++;}sort(a,a+j);if((K-negative)%2==1)a[0]=-a[0];}int sum=0;//求和for(i=0;i<=j-1;i++){//cout<<a[i]<<" ";sum+=a[i];}cout<<sum;return 0;
}

例題八、加油站

力扣題目鏈接

#include<iostream>
#include<cstdio>
#include <bits/stdc++.h>
using namespace std;
int main(){int gas[10001]={0};int cost[10001]={0};int ii,jj=0;do{cin>>gas[ii];ii++;}while(getchar()!='\n');do{cin>>cost[jj];jj++;}while(getchar()!='\n');int i=ii;				//i用來表示gas和cost數組的元素個數int cursum=0,totalsum=0,start=0;for(int k=0;k<=i-1;k++){cursum+=gas[k]-cost[k];totalsum+=gas[k]-cost[k];if(cursum<0){start=k+1;cursum=0;}}if(totalsum<0)return -1;return start;
}

例題九、分發糖果

力扣題目鏈接

#include<iostream>
#include<cstdio>
#include <bits/stdc++.h>
using namespace std;
int main(){int rating[10001];int candy[10001];std::fill(std::begin(candy), std::end(candy), 1);int x=0;do{cin>>rating[x];x++;}while(getchar()!='\n');for(int i=0;i<=x-1;i++){if(rating[i+1]>rating[i])candy[i+1]=candy[i]+1;cout<<candy[i]<<" ";}for(int i=x-1;i>=0;i--){if(rating[i-1]>rating[i])candy[i-1]=max(candy[i-1],candy[i]+1);}int sum=0;for(int i=0;i<=x-1;i++){cout<<candy[i]<<" ";sum+=candy[i];}cout<<sum<<endl;return 0;
}
/*
輸入：1 2 2 5 4 3 2
輸出：1 2 1 2 1 1 1 1 2 1 4 3 2 1 14*/

例題十、檸檬水找零

力扣題目鏈接

#include<iostream>
#include<algorithm>
using namespace std;
int main(){int bill[10001];int five=0,ten=0,twenty=0;std::fill(std::begin(bill),std::end(bill),0);int n=0;do{cin>>bill[n];n++;}while(getchar()!='\n');for(int i=0;i<=n-1;i++){if(bill[i]==5)five++;if(bill[i]==10){if(five>0){five--;ten++;}else {cout<<"false"<<endl;return 0;}}if(bill[i]==20){if(ten>0&&five>0){ten--;five--;twenty++;}else if(five>=3){five-=3;twenty++;}else {cout<<"false"<<endl;return 0;}}}cout<<"true"<<endl;return 0;
}

用return 0結束程序