首页 > 试题广场 >

小美的数组删除

[编程题]小美的数组删除

热度指数：5149 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,\,$ 小美有一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，他可以对数组进行如下操作：
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ ● 删除第一个元素 $a_1$ ，同时数组的长度减一，花费为 $x$ 。

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ ● 删除整个数组，花费为 $k\times \operatorname{MEX}(a)$ （其中 $\operatorname{MEX}(a)$ 表示 $a$ 中未出现过的最小非负整数。例如 $[0,1,2,4]$ 的 $\operatorname{MEX}$ 为 $3$ ）。

$\,\,\,\,\,\,\,\,\,\,$ 小美想知道将 $a$ 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入三个正整数  代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。
第二行输入  个整数 ，表示数组元素。
除此之外，保证所有的  之和不超过 。

输出描述:

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

示例1

输入

1
6 3 3
4 5 2 3 1 0

输出

说明

若不执行操作一就全部删除，，花费  ；
若执行一次操作一后全部删除，，花费  ；
若执行两次操作一后全部删除，，花费  ；
若执行三次操作一后全部删除，，花费  ；
若执行四次操作一后全部删除，，花费  ；
若执行五次操作一后全部删除，，花费  ；
若执行六次操作一，，花费  ；

算法知识视频讲解

Java

偶就要搞开发

刚开始写很容易越界，得不断debug

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
    int k, x;
    List arr;
    int[] counts;
    public static void main(String[] args) {
        Main m = new Main();
        m.task();
    }
    public void task() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int T = Integer.parseInt(br.readLine());
            for (int i = 0; i < T; ++i) {
                List first = Arrays.stream(br.readLine().split(" "))
                                      .map(Integer::parseInt)
                                      .collect(Collectors.toList());
                k = first.get(1);
                x = first.get(2);
                arr = Arrays.stream(br.readLine().split(" "))
                      .map(Integer::parseInt)
                      .collect(Collectors.toList());
                counts = new int[first.get(0) + 1];
                for (int num : arr) {
                    ++counts[num];
                }
                int MEX = counts.length; // 默认都存在
                for (int j = 0; j < counts.length; ++j) {
                    if (counts[j] == 0) {
                        MEX = j;
                        break;
                    }
                }
                System.out.println(minCost(0, MEX));
            }
        } catch (IOException e) {
        }
    }
    //递归
    private long minCost(int i, int MEX) {
        if (i == arr.size()) {
            return 0;
        }
        int nextMEX = MEX;
        int elem = arr.get(i);
        if ((--counts[elem] == 0) && (elem < MEX)) {
            nextMEX = elem;
        }
        return Math.min((long)k * MEX, x + minCost(i + 1, nextMEX));
    }
}

编辑于 2025-01-06 22:08:40 回复(0)

Java

梦想201901032038790

import java.util.*;

//字符串匹配问题 美团24秋招第一场笔试
public class Main {
    //第一题
    public String matchID(String s) {
        if (s.matches("^[a-zA-Z][0-9]+$")) {
            return "standard";
        } else if (s.matches("^[0-9][a-zA-Z]+$")) {
            return "special";
        } else if (s.matches("^[a-zA-Z][a-zA-Z0-9]+$")) {
            return "mix";
        } else {
            return "invalid";
        }
    }

    //第三题
    long[] mexAns;
    public long deletePayment(long[] nums, long k, long x) {
        int n = nums.length;
        if (n == 0) return 0;
        mexAns=null;
        long ans = Long.MAX_VALUE;
        long payment = Math.min(k * mex(nums, 0), (long) n * x);
        if (payment == 0) return 0;
        for (int i = 1; i < n; i++) {
            ans = Math.min(ans, payment);
            payment = (long) i * x + k * mex(nums, i);
        }

        return ans;
    }


    //mex函数测试通过
    public long mex(long[] nums, int i) {
        if(mexAns == null) {
            mexAns = mexList(nums);
        }
        return mexAns[i];
    }

    public long[] mexList(long[] nums) {
        int n = nums.length;
        if (n == 0) return new long[0];
        Set<Long> set = new HashSet<>();

        long[] dp = new long[n];
        dp[n - 1] = nums[n - 1] == 0 ? 1 : 0;
        set.add(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (dp[i + 1] < nums[i]) {
                dp[i] = dp[i + 1];
                set.add(nums[i]);
            } else {
                long mex = dp[i + 1];
                set.add(nums[i]);
                while (set.contains(mex)) {
                    mex++;
                }
                dp[i] = mex;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Main obj = new Main();
        Scanner sc = new Scanner(System.in);
        String nstr = sc.nextLine();
        int n = Integer.parseInt(nstr);
        for (int i = 0; i < n; i++) {
            String str2 = sc.nextLine();
            String[] lenKX = str2.split(" ");
            int len = Integer.parseInt(lenKX[0]);
            long[] nums = new long[len];

            int k = Integer.parseInt(lenKX[1]);
            int x = Integer.parseInt(lenKX[2]);
            String numsStr = sc.nextLine();
            String[] numStr = numsStr.split(" ");

            for (int h = 0; h < len; h++) {
                nums[h] = Long.parseLong(numStr[h]);
            }
            System.out.println(obj.deletePayment(nums, k, x));
        }
//        long[] nums = {4, 5, 2, 3, 1, 0};
//        int k = 3;
//        int x = 3;
//        System.out.println(obj.mex(nums, 0));
//        System.out.println(obj.deletePayment(nums, 3, 3));
    }
}

题目的思路不难，就按照示例的步骤遍历一变数组。重点在于MEX函数的复杂度优化。

三个细节点：

1. 用long保存答案，否则会溢出导致你只能通过2个测试用例

2. 降低MEX的复杂度，并计算一遍MEX将结果保存起来，在遍历数组时让MEX的复杂度为O(1), 整体下来算法的复杂度为O(n) MEX O(N),deletePayment O(N)

3. 删除数组只能从左到右依次删除，求MEX可以从数组尾端向前进行动态规划（可能也不是，本人实力有限照着动态规划套用）

再有就是一些IO上的细节，比如对于多组数据需要每次重制mexList，等等。希望能帮助到大家。

发表于 2024-09-20 23:54:48 回复(0)

Java

終わる

坑在于整型溢出

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int j = 0; j < T; j++) {
            int n = in.nextInt();
            int k = in.nextInt();
            long x = in.nextLong();
            int[] cnt = new int[n + 1];
            int[] arr = new int[n];
            for (int i = 0; i < n; i ++) {
                int val = in.nextInt();
                arr[i] = val;
                cnt[val]++;
            }
            long mex = n;
            for (int i = 0; i <= n; i++) {
                if (cnt[i] == 0) {
                    mex = i;
                    break;
                }
            }
            long minCost = k * mex;
            for (int i = 0; i < n; i++) {
                cnt[arr[i]] --;
                if (arr[i] < mex && cnt[arr[i]] == 0) {
                    mex = arr[i];
                }
                long newRes = (i + 1) * x + mex * k;
                minCost = Math.min(minCost, newRes);
            }
            System.out.println(minCost);
        }
    }
}

发表于 2024-09-02 09:12:24 回复(0)

Java

匿名用尸

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        StringBuilder sb = new StringBuilder();
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            long k = in.nextInt();
            long x = in.nextInt();
            // System.out.println("n:"+n+", k:"+k+", x:"+x);
            HashSet<Integer> set = new HashSet<>();
            int[] as = new int[n];
            for (int j = 0; j < n; j++) {
                as[j] = in.nextInt();
            }
            long min = x * n;
            int cur = 0;
            for (int j = n - 1; j >= 0; j--) {
                set.add(as[j]);
                while (set.contains(cur)) {
                    cur++;
                }
                min = Math.min(x * j + k * cur, min);
                // System.out.println(set);
                // System.out.println("min:"+min+", cur:"+cur);
            }
            sb.append(min);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

发表于 2024-08-17 00:33:30 回复(2)

Java

心死了嘴没死

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T =in.nextInt();
for(int z=0;z<T;z++){
int n =in.nextInt();
int k =in.nextInt();
int x =in.nextInt();
int[] nums =new int[n];
for(int i=0;i<n;i++){
nums[i]=in.nextInt();
}
solve(n,k,x,nums);
}

in.close();
}

static void solve(int n, int k, int x, int[] nums){
long[] mex = MEX(n,nums);
long[] dp = new long[n+1];
for(int i=n-1;i>=0;i--){
dp[i] = Math.min(mex[i]*k,x+dp[i+1]);
}
System.out.println(dp[0]);
}

static long[] MEX(int n, int[] nums){
Set<Integer> set= new HashSet<>();
long[] mex = new long[n];
mex[n-1]= nums[n-1]==0? 1: 0;
if(nums[n-1]>mex[n-1])
set.add(nums[n-1]);
for(int i=n-2;i>=0;i--){
if(nums[i]!=mex[i+1]){
mex[i]=mex[i+1];
if(nums[i]>mex[i])
set.add(nums[i]);
}else{
int tmp = nums[i]+1;
while(set.contains(tmp)){
tmp++;
}
mex[i]=tmp;
if(nums[i]>mex[i])
set.add(nums[i]);
}
}
return mex;
}
}

发表于 2024-08-16 17:25:23 回复(0)

提交观点

问题信息

难度：

6条回答 280收藏 3527浏览

小美的数组删除

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题