lc230 c&d

5691. 通过最少操作次数使数组的和相等

​ $10^5$，考虑$O(n),O(nlogn)$

因为没有单调性，考虑贪心$O(n)$

枚举答案。

如果$sum>ans$ 考虑用$6,5,4\dots ,2$ 按顺序减差值。

否则用$1,2,3,4,5$逆序减差值。

class Solution {
public: 
    int fun(vector<int>&h,int s){
        int sum=0,ans=0;
        for(int i=1;i<7;i++) sum+=h[i]*i;
        if(sum>s){
            int x=sum-s;
            for(int i=6;i>1;i--){
                int t=i-1;
                if(t*h[i]>=x) return ans+(x+t-1)/t;
                x-=t*h[i];
                ans+=h[i]; 
            }
        }
        else {
            int x=s-sum;
            for(int i=1;i<6;i++){
                int t=6-i;
                if(t*h[i]>=x) return ans+(x+t-1)/t;
                x-=t*h[i];
                ans+=h[i];
            }
        }
        return ans;
    }
    int minOperations(vector<int>& a, vector<int>& b) {
        int n=a.size(),m=b.size();
        if(n>m) return minOperations(b,a);
        if(6*n<m) return -1;
        vector<int>c(7),d(7);
        int ans=1e9;
        for(auto i:a) c[i]++;
        for(auto i:b) d[i]++;
        for(int i=m;i<=6*n;i++){
            ans=min(ans,fun(c,i)+fun(d,i));
        }
        return ans;
    }
};

---

5692. 车队 II

凸包维护。

class Solution {
public:
    struct node{
        double x,y;
    };
    double cross(node &a,node &b,node&c){
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    vector<double> getCollisionTimes(vector<vector<int>>& a) {
        int n=a.size();
        vector<node>s(n+1);
         vector<double> ans(n);
        int top=0;
        for(int i=n-1;~i;i--){
            node c={1.0*a[i][0],1.0*a[i][1]};
            while(top>=2&&cross(c,s[top],s[top-1])<=0) top--;
            if(!top) ans[i]=-1;
            else {
                auto &d=s[top];
                if(c.y<=d.y) ans[i]=-1;
                else {
                    ans[i]=(d.x-c.x)/(c.y-d.y);
                }
            }
            s[++top]=c;
        }
        return ans;
    }
};