微软3.25笔试第一题解法

这个贪心思路有问题，感谢大佬提醒，已经发现反例

6
2
3 4 7 7 9 10 

• 微软笔试第一题解法思路：
  • 先用map记录每种数字的个数，若存在超出队伍总数的数字则-1
  • 对于刚好每个队伍都必须放一个的数字单独记录再all_min和all_max里，作为初始化每个队伍最大最小值的初值（若不存在就是INT_MAX和INT_MIN）
  • team[m][3],记录m个队伍的最小值，最大值以及剩余的位置数
  • 接下来就是贪心的把小的数字从队伍0放到队伍m-1; 大的数字从m-1放到0；这样可以保证大的数字尽可能的出现一个队伍里，小的数字也尽可能出现在队伍里，使得每支队伍的max-min是最小的；
  • 最后所有队伍的max-min相加得到ans

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5+5;
const double inf = 1e12;

/*
12
4
5 10 4 8 3 6 5 10 4 8 3 6

2
2
1 1

4
1
1 1 1 1

4
2
1 1 2 2

9
3
3 4 5 6 7 8 8 8 10

9
3
3 4 5 5 5 8 8 8 10

9
3
3 4 5 5 5 8 8 8 10

8
2
10 10 5 5 5 8 8 8

4
4
1 2 3 4

1
1
1

*/

int a[maxn];
map<int, int> mp;

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
        mp[a[i]] ++;
    }
    int m = n / k;
    int all_min = INT_MAX, all_max = INT_MIN;
    vector<int> del;
    for(auto &item : mp){
        if(item.second > m){
            printf("-1\n");
            return 0;
        }
        if(item.second == m){
            all_min = min(all_min, item.first);
            all_max = max(all_max, item.first);
            k--;
            del.push_back(item.first);
        }
    }
    for(int &key : del) mp.erase(key);
    int team[m][3];
    for(int i=0; i<m; i++){
        team[i][0] = all_min;
        team[i][1] = all_max;
        team[i][2] = k;
    }
    vector<pair<int, int> > v;
    for(auto &item : mp){
        v.push_back({item.first, item.second});
    }
    int l = 0, r = v.size()-1;
    while(l <= r){
//        up to down
        int i = 0;
        for(int j=0; j<v[l].second; j++){
            while(i + j < m && !team[i+j][2]) i++;
            if(i + j >= m){
                printf("-1\n");
                return 0;
            }
            team[i+j][0] = min(team[i+j][0], v[l].first);
            team[i+j][1] = max(team[i+j][1], v[l].first);
            team[i+j][2]--;
        }
        l++;
        if(l > r) break; 
//        down to up
        i = m-1;
        for(int j=0; j<v[r].second; j++){
            while(i-j >= 0 && !team[i-j][2]) i--;
            if(i-j < 0){
                printf("-1\n");
                return 0;
            }
            team[i-j][0] = min(team[i-j][0], v[r].first);
            team[i-j][1] = max(team[i-j][1], v[r].first);
            team[i-j][2]--;
        }
        r--;
    }
    int ans = 0;
    for(int i=0; i<m; i++){
//        cout<<team[i][0]<<", "<<team[i][1]<<endl;
        ans += team[i][1] - team[i][0];
    } 
    printf("%d\n", ans);
    return 0;
}