三、アルゴリズム分類経典テーマ練習:欲張りアルゴリズム

貪欲法:絶えず貪欲な選択は現在の最善策で、貪欲アルゴリズムを使う前提条件は現在の最良解、すなわちグローバル最適解です.455.お菓子を配る

class Solution {
     
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
     
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookies = 0;
        while(child < g.size() && cookies < s.size()){
     
            if(g[child] <= s[cookies]) child++;
            cookies++;
        }
        return child;
    }
};

376.ウィービングシーケンス

class Solution {
     
public:
    int wiggleMaxLength(vector<int>& nums) {
     
        if(nums.size()<2) return nums.size();
        int max_len = 1;
        static const int BEGIN = 0;
        static const int UP = 1;
        static const int DOWN = 2;
        int state = BEGIN;
        for(int i = 1; i < nums.size(); ++i){
     
            switch(state){
     
                case BEGIN:
                    if(nums[i-1] < nums[i]){
     
                        state = UP;
                        max_len++;
                    }else if(nums[i-1] > nums[i]){
     
                        state = DOWN;
                        max_len++;
                    }
                    break;
                case UP:
                    if(nums[i-1] > nums[i]){
     
                        state = DOWN;
                        max_len++;
                    }
                    break;
                case DOWN:
                    if(nums[i-1] < nums[i]){
     
                        state = UP;
                        max_len++;
                    }
                    break;
            }
        }
        return max_len;
    }
};

402.K桁の数字をずらす

class Solution {
     
public:
    string removeKdigits(string num, int k) {
     
        vector<int> S;
        string res = "";
        for(int i = 0; i < num.size(); ++i){
     
            int number = num[i]-'0';
            while(S.size()!=0 && k>0 && S[S.size()-1]>number){
     
                k--;
                S.pop_back();
            }
            if(number!=0 || S.size()!=0) S.push_back(number);
        }
        while(S.size()!=0 && k>0) S.pop_back(),k--;
        for(int i = 0; i < S.size(); ++i) res.append(1,'0'+S[i]);
        if(res=="") res = "0";
        return res;
    }
};

55.ジャンプゲーム

class Solution {
     
public:
    bool canJump(vector<int>& nums) {
     
        vector<int> index;
        for(int i = 0; i < nums.size(); ++i){
     
            index.push_back(i+nums[i]);
        }
        int jump = 0;
        int max_index = index[0];
        while(jump<nums.size() && jump<=max_index){
     
            if(max_index < index[jump]) max_index = index[jump];
            jump++;
        }
        if(jump == nums.size()) return true;
        return false;
    }
};

45.ジャンプゲームII

class Solution {
     
public:
    int jump(vector<int>& nums) {
     
        if(nums.size()<2) return 0;
        int jump_min = 1;
        int cur_max_idx = nums[0];
        int pre_max_idx = nums[0];
        for(int i = 0; i < nums.size(); ++i){
     
            if(i > cur_max_idx){
     
                jump_min++;
                cur_max_idx = pre_max_idx;
            }
            if(pre_max_idx < nums[i]+i){
     
                pre_max_idx = nums[i]+i;
            }
        }
        return jump_min;
    }
};

452.最小数の矢で風船を爆発させる

class Solution {
     
public:
    int findMinArrowShots(vector<vector<int>>& points) {
     
        if(points.size()==0) return 0;
        sort(points.begin(), points.end());
        int shoot_num = 1;
        int begin = points[0][0];
        int end = points[0][1];
        for(int i = 1; i < points.size(); ++i){
     
            if(points[i][0] <= end){
     
                begin = points[i][0];
                if(points[i][1] < end){
     
                    end = points[i][1];
                }
            }else{
     
                shoot_num++;
                begin = points[i][0];
                end = points[i][1];
            }
        }
        return shoot_num;
    }
};

poj 2431 Expeditionhttp://poj.org/problem?id=2431

#include 

#include 
#include 
#include 

bool cmp(const std::pair<int, int> &a, const std::pair<int ,int> &b) {
     
    return a.first > b.first;
}

int get_minimum_stop(int L, int P, std::vector<std::pair<int, int> > &stop){
     
	std::priority_queue<int> Q;
	int result = 0;
	stop.push_back(std::make_pair(0, 0));
	std::sort(stop.begin(), stop.end(), cmp);
	for (int i = 0; i < stop.size(); i++){
     
		int dis = L - stop[i].first;
		while (!Q.empty() && P < dis){
     
			P += Q.top();
			Q.pop();
			result++;
		}
		if (Q.empty() && P < dis){
     
			return -1;
		}
		P = P - dis;
		L = stop[i].first;
		Q.push(stop[i].second);
	}
	return result;
}

int main(){
     
	std::vector<std::pair<int, int> > stop;
	int N;
	int L;
	int P;
	int distance;
	int fuel;
	scanf("%d", &N);
	for (int i = 0; i < N; i++){
     
		scanf("%d %d", &distance, &fuel);
		stop.push_back(std::make_pair(distance, fuel));
	}
	scanf("%d %d", &L, &P);
	printf("%d
", get_minimum_stop(L, P, stop));
	return 0;
}