前言

感覺開始打cf了以后貪心的能力有了明顯的提升，讓我們謝謝cf的感覺場。

一、跳躍游戲 II

class Solution {
public:int jump(vector<int>& nums) {int n=nums.size();//怎么感覺這個題也在洛谷上刷過(?)int cur=0;//當前步最遠位置int next=0;//多跳一步最遠位置int ans=0;for(int i=0;i<n;i++){//到不了i位置 -> 跳if(cur<i){ans++;cur=next;}next=max(next,i+nums[i]);}return ans;}
};

真感覺這個題在洛谷上刷到過類似的。

這類問題就是設置一個當前步數內能到的最遠距離和再多跳一步能到的最遠距離。然后只要當前步數內跳不到了，就增加步數繼續跳，每次看從當前位置能否把next更新得更大即可。

這個說白了就是動態規劃的思想。

二、灌溉花園的最少水龍頭數目

class Solution {
public:int minTaps(int n, vector<int>& ranges) {//right[i]:從左側最遠i到右側最遠的位置jvector<int>right(n+1);for(int i=0;i<=n;i++){int left=max(0,i-ranges[i]);right[left]=max(right[left],i+ranges[i]);}int cur=0;//當前數量的水龍頭最右影響的位置int next=0;//多打開一個的最右位置int ans=0;for(int i=0;i<n;i++){//開能從i往右覆蓋最遠的水龍頭next=max(next,right[i]);if(i==cur)//來到最右邊界{if(next>i)//后續能覆蓋{cur=next;ans++;}else{return -1;}}}return ans;}
};

這個題要注意的是，單點滿足是不符合題意的，必須要區間覆蓋才行。

整體思路是首先構建一個right數組，含義是從i位置開始能覆蓋到的最右位置，然后就把這道題轉化成了上一道題。

具體就是每次先找出每個水龍頭能覆蓋到的最左位置，然后就能去看這個水龍頭能不能把這個最左位置的right更新得更遠。之后就是和上個題一樣設置cur和next兩變量，不一樣的是，每次先更新next，然后直到此時來到了最右邊界，才去看是否再開一個能覆蓋后續。如果能覆蓋，即next大于i，那就多開一個，否則說明當前水龍頭到下一個水龍頭中間的位置是覆蓋不到的，那就直接返回-1即可。

三、過河問題

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;/*
這題讓我想到了小時候玩的一個游戲兩個策略：
1.讓最小的人一趟一趟送
2.讓最小的兩個人先過去，然后其中一人把船開回來，再讓最大的兩個人過去，再讓另一個人回來*/void solve()
{int n;cin>>n;vector<int>a(n);for(int i=0;i<n;i++){