4399笔试凉

三道题，感觉写的都不对

第一题改装二分，一见logn一般都是二分

第二题，应该是dp或贪心，不太会

第三题，感觉不应该是我这个思路

class Solution {

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int low=0;
        int high=nums.size()-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(nums[mid]==target)
            high=mid-1;
            if(nums[mid]<target)
            low=mid+1;
            else
            high=mid-1;
        }
        int low2=0,high2=nums.size()-1;
        swap(low2,low);swap(high2,high);
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(nums[mid]==target)
            low=mid+1;
            if(nums[mid]<target)
            low=mid+1;
            else
            high=mid-1;
        }
        if(low2<=low)
        return {low2,low};
        return {-1,-1};
    }

};
int coinChange(vector<int>& coins, int amount) {
    if(amount==0)return 0;
    int ret=0;
    vector<int> cnt_conins(coins.size());//记录每个硬币选了几个
    sort(coins.begin(),coins.end(),greater<int>);//降序，从大到小选硬币
    
    int have=0;//剩余
    while(1)
    {
        cnt_conins[0]=amount/coins[0];
        have=amount%cnt_conins[0];
        for(int i=1;i<coins.size();++i)
        {
            cnt_conins[i]=have/coins[i];
            have=have%cnt_conins[i];
        }
    }
    
}
/*
思路:设置全局nowtime，每过一小时nowtime++，同时检查当前是否有新的task到来，
当有新的task到来时将其加入优先队列，这个优先队列以处理时长为优先级越小的越靠前
每项任务被处理后其处理时间task.p就要相应减小，为0时，将当前nowtime作为该id任务的测试时间，加入vector
当没有任务到来且优先队列已为空时，返回结果
*/
vector<vector<int>> processTasks(vector<Task>& tasks) {
    priority_queue<Task,vector<Task>,[](Task t1,Task t2){return t1.p<t2.p;}> q;
    vector<vector<int>> ret;//返回的结果集
    
    int nowtime=0;
    int n=tasks.size();
    tasks.sort(tasks.begin(),tasks.end(),[](Task t1,Task t2){return t1.r<t2.r;});//按到来时间升序
    int cnt=0;//已被处理的任务数
    vector<bool> final(n);//标记某任务是否被加入q
    nowtime=tasks[0].r;
    while(1)
    {
        for(int i=0;i<n;++i)
        {
            if(tasks[i].r<=nowtime&&final[i]==false)
            {
                q.push(task[i]);
                final[i]=true;
            }
        }
        nowtime++;
        auto& top_task=q.front();
        top_task.q--;
        if(top.top_task.q==0)
        {
            q.pop();
            ret.push_back({top_task.id,nowtime});
            cnt++;
        }
        sort(q.begin(),q.end(),[](Task t1,Task t2){return t1.p<t2.p;});
        if(cnt==n)break;
    }
    return ret;
}