leetcode 1300. 转变数组后最接近目标值的数组和

梦里梦外; 2023-02-18 01:53 23阅读 0赞

思路：这种找最小满足条件的数，一般都是二分来做。

首先枚举value。枚举好以后，为了能在O(logn)的时间内计算出和，可以先对原数组进行排序，然后二分找一下。

最后，答案可能是l或者r。具体需要比较一下。

class Solution {
    public:
        int findBestValue(vector<int>& arr, int target) {
            sort(arr.begin(),arr.end());
            int n=arr.size();
            int sum[n+1];
            int M=0;
            memset(sum,0,sizeof(sum));
            for(int i=0;i<n;i++)
            {
                M=max(M,arr[i]);
                if(i==0) sum[i]=arr[i];
                else
                {
                    sum[i]=sum[i-1]+arr[i];
                }
            }
            int l=0,r=M;
            int ans=-1;
            while(l<=r)
            {
                int mid = (l+r)>>1;
                int k = lower_bound(arr.begin(),arr.end(),mid)-arr.begin();
                //cout<<k<<endl;
                int s;
                if(k==0) s=n*mid;
                else s= sum[k-1]+(n-k)*mid;
                if(s>target)
                {
                    r=mid-1;
                }
                else if(s<target)
                {
                    l=mid+1;
                }
                else
                {
                    ans=mid;
                    break;
                }
            }
            //cout<<l<<" "<<r<<endl;
            if(ans==-1)
            {
                swap(l,r);
                int k=lower_bound(arr.begin(),arr.end(),l)-arr.begin();
                int s1=0;
                if(k==0) s1=n*l;
                else s1=sum[k-1]+(n-k)*l;
               // cout<<".. "<<k<<endl;
                k=lower_bound(arr.begin(),arr.end(),r)-arr.begin();
                int s2=0;
                if(k==0) s2=n*r;
                else s2=sum[k-1]+(n-k)*r;
                // cout<<"... "<<k<<endl;
            //    cout<<l<<" "<<r<<endl;
            //     cout<<s1<<" "<<s2<<endl;
                if(abs(s1-target)>abs(s2-target)) ans=r;
                else if(abs(s1-target)==abs(s2-target)) ans=min(l,r);
                else ans=l;
    
            }
            return ans;
        }
    };