狗家电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. double SalaryCut(vector<int>& test, int budge){
   
2.     sort(test.begin(),test.end(),greater<int>());
   
3.     int tsum = accumulate(test.begin(),test.end(),0);
   
4.     int cut = tsum - budge;
   
5.     int rsum = 0;
   
6.     cout<< cut<<endl;
   
7.     for(int i =0; i <test.size();i++){
   
8.         rsum +=test[i];
   
9.         if (rsum - test[i]*(i+1) >= cut){
   
10.             return (rsum - test[i] - cut)/(double)i;
    
11.         }
    
12.     }
    
13.     return -1;
    
14. }

复制代码

想到一个用Greedy的解法， 未排序 nlogn，排序O(n)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. public int maximumK (int[] salary, int budget) {
   
2.         Arrays.sort(salary);
   
3.         int N = salary.length;
   
4.         int sum = 0;
   
5.         for (int i = 0; i < N-1; i++) {
   
6.                 sum += salary[i];
   
7.                 int expect = (budget - sum)/(N-i-1);
   
8.                 if (salary[i+1] >= expect) return expect;
   
9. }
   
10. return -1;
    
11. }
    

复制代码

1. int decreaseSalary(int budget, vector<int> salaries) {
   
2.     priority_queue<int, vector<int>> pq;
   
3.     int sum = 0;
   
4.     for(int s:salaries) {
   
5.         sum += s;
   
6.         pq.push(s);
   
7.     }
   
8.     int tops = 0;
   
9.     int cnt = 0;
   
10.     while(cnt == 0 || (budget + tops - sum )/cnt < pq.top()) {
    
11.         tops += pq.top();
    
12.         cnt ++;
    
13.         pq.pop();
    
14.     }
    
15.     return (budget + tops - sum )/cnt;
    
16. 
    
17. }

复制代码

感觉priority queue 也可以 时间也是O(logn)