2022年4月16日网易笔试

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
void wangyi_4_16_second(long long n, long long k, long long x){
    long long maximum = 0, minimum = 0;
    for(int i = 1; i <= n; ++i){
        minimum += i;
        if(maximum <= 1e9) maximum += (k - i + 1);
    }
    // n > k , x大于可能的最大值或小于可能的最小值时无解，例：[1, 2, 3, 4, 5, 6, 7], n = 3，k = 7，x = 3和x = 19时无解   
     if(n > k || x < minimum || maximum < x) {
        printf("-1\n");
        return ;
    }
        // 可以证明经上面的判断后一定有解
    int a = (x - minimum) / n;// a为x和最小可能值差几个n，差几个就整体向后移动几次，并可以证明最大的数不会移动出k
    int b = (x - minimum) % n;// b为余数，就是移动过后的数组还和x差多少，差多少我就用刚好比移动过后的数组中最大的数大一的这个数替换数组中的一个数
                                         // 显然被替换的数为n + a + 1 - b,可以证明 刚好比移动过后的数组中最大的数大一的这个数 也不会超出k的范围
    int res[100005], cnt = 0;
        // 将1-n这n个数每个数加a，并将n + a + 1 - b这个数替换成n + a + 1 即为最终答案
    for(int i = 1;i <= n; ++i)
        if(i + a != n + a + 1 - b) res[cnt++] = i + a;
    if(cnt != n) res[cnt++] = n + a + 1;
    for(int i = 0 ; i < cnt - 1; ++i) printf("%d ",res[i]);
    printf("%d\n", res[cnt - 1]);
}

int main()
{
    wangyi_4_16_second(4, 6, 15);
    return 0;
}

function getValue(a1, a2){
    let two = 0;
    let five = 0;
    while(a1 % 2 == 0){
        two += 1;
        a1 /= 2;
    }
    while(a1 % 5 == 0){
        five += 1;
        a1 /= 5;
    }
    while(a2 % 2 == 0){
        two += 1;
        a2 /= 2;
    }
    while(a2 % 5 == 0){
        five += 1;
        a2 /= 5;
    }
    return Math.min(two, five);// 2因子和 5因子 少的
}
function getFather(father, x){
    if(father[x] == x) return x;
    father[x] = getFather(father, father[x]);
    return father[x];
}
function wangyi_4_16_third(n, m, a, edge){
    let res = 0;
    let sum = 0;
    // 边按照收益从小到大排序
    edge.sort(function(e1, e2){
        return getValue(a[e1[0] - 1], a[e1[1] - 1]) - getValue(a[e2[0] - 1], a[e2[1] - 1]);
    });
    // 初始化父亲数组
    let father = [0];
    for(let i = 1; i <= n; i += 1) father.push(i);
    // 合并
    for(let i = 0; i < m; i += 1){
        let value = getValue(a[edge[i][0] - 1], a[edge[i][1] - 1]);
        // sum 计算删除所有边的收益
        sum += value;
        // 分别计算当前边的两个节点是否连同 
        let f1 = getFather(father, edge[i][0]);  
        let f2 = getFather(father, edge[i][1]);
        // 如果不连通，则连通他们，res为连通此图的最小收益
        if(f1 != f2){
            father[f1] = f2;
            res += value;
        } 
    }
    return sum - res;// 所有边的收益-连通此图的最小收益 即为删掉边的最大收益
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int wangyi_4_16_forth(){
    // 待补充
}
int main()
{
    
    return 0;
}