# 数据结构与算法-贪心算法

2019/08/25 13:13

#include  "pch.h"
#include <iostream>
#include <stdio.h>

int main()
{
const int RMB[] = { 200, 100, 20, 5, 1 };
const int NUM = 5;
int X = 628;
int count = 0;
for (int i = 0; i < NUM; i++) {
int use = X / RMB[i];
count += use;
X = X - RMB[i] * use;
printf("需要面额为%d的%d张, ", RMB[i], use);
printf("剩余需要支付金额%d.\n", X);
}
printf("总共需要%d张\n", count);
return 0;
}

# 二、摇摆序列

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

# 三、移除K个数字

class Solution {
public:
string removeKdigits(string num, int k) {
std::vector<int> S;   //S是整型数组，当栈用
std::string result = "";
for (int i = 0 ; i < num.length(); i++)
{
int number = num[i] - '0'; //字符型num转化为整数
while (S.size() != 0 && S[S.size() -1] > number && k > 0){
S.pop_back();
k--;
}
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++)
{
result.append(1, '0' + S[i]); //将整数转化为字符
}
if(result == ""){
result = "0";
}
return result;
}
};

# 四、跳跃游戏

class Solution {
public:
bool canJump(vector<int>& nums) {
std::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;
}
};

# 六、最优加油方法

#define _CRT_SECURE_NO_WARNINGS
#include  "pch.h"
#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>

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 (P < dis && Q.empty()) {
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\n", get_minimum_stop(L, P, stop));
return 0;
}

0
0 收藏

0 评论
0 收藏
0