数据结构与算法：贪心（二）

前言

要加快速度啊！！

一、最短无序连续子数组

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size();

        int Max=-1e9;
        int right=-1;//最右不符合的位置
        for(int i=0;i<n;i++)
        {
            if(Max>nums[i])//遇到不符合递增规律的数
            {
                right=i;
            }
            Max=max(Max,nums[i]);
        }

        int Min=1e9;
        int left=n;//最左不符合的位置
        for(int i=n-1;i>=0;i--)//从后往前遍历
        {
            if(Min<nums[i])//遇到不符合递减规律的数
            {
                left=i;
            }
            Min=min(Min,nums[i]);
        }

        //最左不符合的位置到最优不符合的位置就是需要排序的区域
        return max(0,right-left+1);
    }
};

我是伞兵……无穷小的写法是“-1e9”！！

上来这个题的思路就很抽象，因为要抓出一个区间进行排序，而观察递增数组的特点可以发现，如果从前往后遍历，后一个数必然必前一个数大，从后往前遍历的话前一个数也必然比后一个数小。所以思路就是，先从前往后遍历求最大值，当发现不符合递增规律的位置，即最大值更新不了时就记录。接着从后往前遍历求最小值，同样当发现不符合递减规律的位置就记录。所以此时的区间就是不符合递减规律的最左位置到不符合递增规律的最右位置。注意最后要再和0比较一下，即整个数组已经递增，不需要排序。

二、最小区间

class Solution {
public:

    struct Node
    {
        int val;//数值
        int i;//来自哪一个列表
        int j;//列表的第几个元素
    };

    static bool cmp(const Node&a,const Node&b)
    {
        return a.val!=b.val?a.val<b.val:a.i<b.i;
    }

    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k=nums.size();

        set<Node,decltype(&cmp)>s(cmp);

        for(int i=0;i<k;i++)
        {
            Node n={nums[i][0],i,0};
            s.insert(n);
        }

        //贪心：区间每次以这k个数的最小值开头，以最大值结尾

        int len=1e9;//长度

        int left=0;
        int right=0;

        Node Max,Min;

        while(s.size()==k)//必须时刻保证有k个元素
        {
            Max=*s.rbegin();//最大值
            Min=*s.begin();//最小值
            s.erase(*s.begin());

            if(Max.val-Min.val<len)//能更新到更小
            {
                len=Max.val-Min.val;
                left=Min.val;
                right=Max.val;
            }

            if(Min.j+1<nums[Min.i].size())//将最小值的下一个放入
            {
                Node n={nums[Min.i][Min.j+1],Min.i,Min.j+1};
                s.insert(n);
            }
        }

        vector<int>ans={left,right};
        return ans;
    }
};

无语了忘了结构体怎么写了……

这个题我感觉cpp会有更快的写法，照搬左老师的java版常数时间太大了……

这个题的贪心思路就是让这个区间每次以这k个数的最小值开头，以最大值结尾，然后每次弹出最小值，把这个最小值所在位置的下一个数加进来，中间统计最短区间长度即可。所以就是设置一个set同时维护最大值和最小值，而因为在弹出时要找到对应的数组和位置，所以往set里存的时候要存一个结构体。

三、组团买票

景区m个项目，第i个项目有两个参数：game[i]={Ki,Bi}，Ki、Bi一定是正数。Ki代表折扣系数，Bi代表票价。当有x个人买票时，每张票的价格为Bi-Ki*x，价格大于等于零。单位共有n个人，每人最多可以选一个项目游玩，求需要准备多少钱，可以满足所有选择情况。

1<=m,n,Ki,Bi<=10^5

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

//公园最大收益
int f(int i,int n,int m,vector<vector<int>>&games,vector<int>&cnts)
{
    if(i==n)
    {
        int ans=0;
        for(int j=0,k,b,x;j<m;j++)
        {
            k=games[j][0];
            b=games[j][1];
            x=cnts[j];
            ans+=max((b-k*x),0);
        }
        return ans;
    }

    int ans=f(i+1,n,m,games,cnts);//不玩
    for(int j=0;j<m;j++)//枚举去哪个项目玩
    {
        cnts[j]++;
        ans=max(ans,f(i+1,n,m,games,cnts));
        cnts[j]--;
    }

    return ans;
}

//暴力解
int solve1(int n,vector<vector<int>>&games)
{
    int m=games.size();
    vector<int>cnts(m);
    return f(0,n,m,games,cnts);
}

//项目
struct Game
{
    int ki;
    int bi;
    int people;
};

//项目收益
int earn(int ki,int bi,int x)
{
    return bi*(x+1)*ki-x*ki;
}

static bool cmp(const Game&a,const Game&b)
{
    return earn(a.ki,a.bi,a.people)>earn(b.ki,b.bi,b.people);
}

//正解
int solve2(int n,vector<vector<int>>&games)
{
    //最保险：公园赚的钱数最大

    //不同人数x来时，每个项目一共赚若干元钱
    //将视角转换成，此时再来一个人，该项目总收益的变化
    //公式：Bi-(x+1)*Ki-x*Ki -&