ccfcsp202303-2题解(不知道贪心算法解答能不能过)

#include<iostream>
using namespace std;
const int N=1010;
int t[N],c[N],allow[N];
int maxfind(int array[],int n)
{
    int maxis=0;
    for(int i=0;i<n;i++)
    {
        maxis=max(maxis,array[i]);
    }
    return maxis;
}

int main()
{

/*
基本输入：
*/
    int n=0,m=0,k=0;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
        cin>>t[i]>>c[i];

    }


/*
主要处理逻辑：在资源够用的情况下，将最长时间的土地开垦时间不断减一

*/
    while(m>=0)
    {
        int timetoquit=0;
        int bigg=maxfind(t,n);
        if(bigg<=k)
        {
            break;
        }
        for(int i=0;i<n;i++)
        {
            if(t[i]==bigg)
            {
                
                if(m<c[i])
                {
                    timetoquit=1;
                    break;
                }
                t[i]--;//第一次做的时候错将判断条件滞后，导致用例错误
                //实际上要先判断再处理！
                m-=c[i];
            }
        }
        if(timetoquit==1)
        {
            break;
        }

    }
    int ans=maxfind(t,n);
    cout<<ans<<endl;
    return 0;

}

时间复杂度为O（n^2）,太复杂，学习一下优化后算法，优化有俩思路，一是使用二分法，二是用最大堆存储最大值。