【Algorithm-Gready】贪心算法

#include <iostream>

using namespace std;

int main(){
    int length=0;
    int arr[1001]={0};
    while(cin>>arr[length++]){
        if(cin.get()=='\n') break;
    }
    if(length==1){
        cout<<0<<endl;
    }else{
        int i=0;
        int res=0;
        while(i<length-1){
            int steps=arr[i];
            //如果能一步到终点
            if(steps>=length-1-i){
                res++;
                break;
            }
            //如果不能一步到终点，有以下操作：
            //1、假设从当前位置的 后一个候选点 出发，就是最优解
            int the_max=arr[i+1];
            //bestPointLoc是the_max对应的出发点(即当前最优解的位置)
            int bestPointLoc=i+1;
            //2、对当前这个点能到达的所有候选点，进行遍历，arr[j]是候选点的能跳数
            //j是后面候选点下标
            for(int j=i+2;j<=i+steps&&j<length-1;j++){
                //选出原则：
                //原则0：去候选点能跳数更大的
                //原则1：尽量走远
                //j-bestPointLoc表示j到当前最优解位置的距离
                //让arr[j]+j-bestPointLoc>=the_max，说明从bestPointLoc点出发也未必能有从位置为i的候选点出发走得远
                if(arr[j]+j-bestPointLoc>=the_max){
                    the_max=arr[j];
                    //bestPointLoc是the_max对应的出发点
                    bestPointLoc=j;
                }
            }
            //跳数加1
            res++;
            //跳到bestPointLoc这个位置
            i=bestPointLoc;
        }
        cout<<res<<endl;
    }
}

#include<iostream>
#include<algorithm>
using namespace std;
struct Area
{
	int left, right;
}area[100],r[100];
bool cmp(Area a,Area b){
	if (a.left < b.left)
		return true;
	else if (a.left == b.left && a.right < b.right)
		return true;
	else  return false;
}
int main() {
	int n,i,cnt=0;
	cin >> n;
	for ( i = 0; i < n; i++) {
		cin >> area[i].left >> area[i].right;
	}
	sort(area, area + n, cmp);
    //左边界的判断点
	int leftPivot = area[0].left - 1;
    //终点
	int end = area[n - 1].right;
	for (i = 0; i < n-1;) {
        //假设当前能得到的最右边界
		int max_rightBorder = area[i].right;
        //记录对应区间
		int max_interval = i;
        //如果下一步的区间的左边 小于 当前的左边界+1
		while (area[i].left <= leftPivot + 1 && i < n) {
            //如果下一步区间的右边，大于当前能达到的最右边界
			if (area[i].right > max_rightBorder) {
                //记录能到达的最大的右端点的值
				max_rightBorder= area[i].right;
                //记录能到达的最大的右端点的区间编号
				max_interval = i;
			}
			i++;
		}
        //更新右的值
		leftPivot = max_rightBorder;
        //数组中记录被选择的区间
		r[cnt++] = area[max_interval];
        //i恢复到从最大处的点开始，如果这步不做，可能会忽略掉一些区间
        //如[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]，最后的[6,8]就会被忽略
		i = max_interval;
		if (leftPivot == end) 
            break;//嘿嘿终于到终点啦~~结束
	}
	for (i = 0; i < cnt; i++){
		cout << r[i].left << " " << r[i].right << endl;
	}
	return 0;
}

3
1 3 2
2 6 3
7 10 1

4

#include<iostream>
#include<algorithm>
using namespace std;
//结构体中包括b,e,t
struct home
{
   	//b开始位置，e结束位置，t要种树数量
	int b,e,t;
}dwelling[105];
//flag用来表示该位置是否有树
int flag[10005]={0},sum;

//种树函数，从尾部x开始倒着种树，种y棵
void growTree(int e,int t)
{
	while(t--)
	{
		flag[e--]=1;
	}
}

//数树函数，用来计算x到y之间有多少棵树
int countTree(int b,int e)
{
	sum=0;
	for(int i=b;i<=e;i++)
		if(flag[i])
			sum++;
	return sum;
}

//排序函数，先按照结束位置从小到大排列
int cmp(home x,home y)
{
	if(x.e<y.e) return 1;
	else if(x.e==y.e&&x.b>y.b) return 1;//结束位置相同，把开始位置大的放在前面
		else return 0;
}
int main()
{
	int n,i,tot=0,tmp;//tot表示所要种的树的总数
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>dwelling[i].b>>dwelling[i].e>>dwelling[i].t;
	sort(dwelling+1,dwelling+1+n,cmp);//进行排序
    //为第一户居民种树，第一户直接从它要求的区间尾部开始种
	growTree(dwelling[1].e,dwelling[1].t);
	tot+=dwelling[1].t; 
	for(i=2;i<=n;i++)
	{
        //如果这个居民的种树的开始位置小于上一个居民的结束位置，则有相交区域
		if(dwelling[i].b<=dwelling[i-1].e)
		{
            //计算出相交位置有多少棵树（intersectNum）
			intersectNum=countTree(dwelling[i].b,dwelling[i-1].e);
            //如果相交位置的树已经大于该居民所要种植的树，则不需要再种树
			if(intersectNum>=dwelling[i].t)
				continue;
			else{
                //否则再从该居民的尾部开始种树，数量为c[i].t-intersectNum
				growTree(dwelling[i].e,dwelling[i].t-intersectNum);
            	//改变tot的值
				tot+=dwelling[i].t-intersectNum;
            }
		}
        //如果没有相交的区域
		else
		{
            //从该居民的结束位置倒着种树
			growTree(dwelling[i].e,dwelling[i].t);
			tot+=dwelling[i].t;
		}
	}
	cout<<tot;
	return 0;
}

#include<bits/stdc++.h>    
using namespace std;    
string res;    
string str;    
void foo(string str,int k){    
    int flag=1;    
    int end=str.length();    
    //用来保留原来数据    
    int length2=end;    
    int k2=k;    
    string str2=str;    
    //需要删除的个数    
    while(k>0){  
        //每次删除一个后，都要重头开始与后面数字比较
        for(int i=0;i<end-1;i++){    
            //如果当前字符大于下一个，当前字符要被删除    
            if(str[i]>str[i+1]){    
                str.replace(i,1,"");    
                //找到了在最后一个字符前面的需要被删除的字符，退出循环并标记    
                flag=0;    
                break;    
            }    
        }    
        //否则删除最后一个字符 （最后一个字符是最大的）   
        if(flag){    
            str.replace(end-1,1,"");  
            end-=1;  
        }    
        k--;    
    }    
    int p1=0,p2=0;    
    string del="";    
    //用来输出原来的字符串和被保留的字符串不同的字符，即是被删除的字符    
    //str是被保留  
    //str2是原始  
    //length2-k2是保留的个数
    while(p1<=length2-k2) {    
        //如果原始字符中有被保留的字符串中字符，则同时移动到下一位    
        if(str[p1]==str2[p2]) {    
            p1++;    
            p2++;    
        }else {    
            //否则将原始中不在被保留字符串中出现的字符构建成一个新串    
            if(del=="")    
                del+=str2[p2];    
            else     
                del=del+" "+str2[p2];    
            p2++;    
        }    
    }    
    cout<<"deleted ";  
    cout<<del<<endl;  
    cout<<"reserve ";  
    cout<<str<<endl;    
}    
int main(){    
    int k;    
    while(cin>>str>>k){    
        int length=str.length();    
        foo(str,k);    
    }    
}    

 #include <iostream>
 #include <algorithm>
using namespace std;
//结构体包含时间和罚款
struct node
{
	int time,penalty;
};
bool cmp(struct node a, struct node b)
 {
    return a.penalty > b.penalty;
}
 struct node arr[10000];
 //某段时间是否被占用 没被占用为0
 int t[10000] = {0}; 
 int main()
 {
    int rewards,n;
    cin>>rewards>>n;
    //扣钱总数
    int penalty_sum = 0;
    for (int i = 0; i < n; i++)
        cin >> arr[i].time;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].penalty;
        penalty_sum += arr[i].penalty;
    }
    //将数组a按罚款大小，降序排序
    sort(arr, arr + n, cmp);
    for (int i = 0; i < n; i++)
    {
        //从某个游戏对应的截止时间开始
        //【背包问题也是倒着开始；如果每个游戏的开始时间不同，这里就不能大于1，而是每个游戏对应的开始时间】
        for (int j = arr[i].time; j >= 1; j--) 
        {
            //t[j]==0说明这段时间可用
            if (t[j] == 0){
                //不用被扣钱
                penalty_sum -= arr[i].penalty;
                //让这段时间被占用
                t[j] = 1;
                //找到了则无需继续找下去，否则需要继续找到一个时间点，来完成任务，如果不存在这个时间点，就会被扣钱
                break;
            }
        }
    }
    cout << rewards - penalty_sum << endl;
 }