欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA CCF-201809-4 再卖菜

程序员文章站 2022-04-15 17:51:01
欢迎访问我的CCF认证解题目录题目思路过程给的是第二天的菜价,求的是第一天字典序最小的菜价,假设第一天的菜价为 a[1]、a[2] ... a[n],第二天的菜价为 b[1]、b[2] ... b[n]。现在是已知b,求a字典序最小的情况,那么看情况应该是DFS进行遍历操作,先枚举出第一个a进行递归操作,然后计算出可能存在的最小a,递归直到找出所有的a。根据题意可知第一天和第二天的关系是:第1位只需满足 1 <= a[0] <= 2*b[0] 即可(价格必须大于0)第2位:...

欢迎访问我的CCF认证解题目录


题目

JAVA CCF-201809-4 再卖菜


思路过程

给的是第二天的菜价,求的是第一天字典序最小的菜价,假设第一天的菜价为 a[1]、a[2] ... a[n],第二天的菜价为 b[1]、b[2] ... b[n]
现在是已知b,求a字典序最小的情况,那么看情况应该是DFS进行遍历操作,先枚举出第一个a进行递归操作,然后计算出可能存在的最小a,递归直到找出所有的a。

根据题意可知第一天和第二天的关系是:

  • 第1位只需满足 1 <= a[0] <= 2*b[0] 即可(价格必须大于0)
  • 第2位:b[0]*2 <= a[0] + a[1] <= b[0]*2 + 1
  • 第3~n-1位:b[index]*3 <= a[index-1] + a[index] + a[index+1] <= b[index]*3 + 2
  • 第n位:b[n]*2 <= a[n-1] + a[n] <= b[n]*2 + 1

注意:

  • 如果只是递归的话会有大量的重复计算,这样只能得80分,需要进行记忆化搜索,加上flag[index][第index-1个商店的价格][第index个商店的价格]进行记忆化,如果第index-1价格和第index价格确定了,那么后面就都是相同的,因为后面价格是通过"int st = b[index]*3 - a[index-1] - a[index], ed = st+2"计算的,只用到了index-1和index,所以如果已经走过了,那么就无需再走。
  • 如果价格没有加 >= 0 的判断,只有30~40分。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Main {

    static int[] a, b;
    // 题目给的是第二天的价格,所以第一天最大可以接近3倍!
    static boolean[][][] flag = new boolean[305][305][305];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        b = new int[n];
        a = new int[n];
        for ( int i = 0; i < n; i++ ) b[i] = in.nextInt();
        // for循环遍历、枚举第一个商店的价格,顺便枚举出第二个商店的价格
        for ( int st = 1; st <= b[0]*2; st++ ) {
            a[0] = st;
            // 没有大于0的判断就只有30分,由公式可知,如果第一个商店的价格确定了,那么第二个商店的价格就只有两种可能。
            if ( b[0]*2-st > 0 && dfs(1, b[0]*2-st) ) break;
            if ( b[0]*2-st+1 > 0 && dfs(1, b[0]*2-st+1) ) break;
        }
        for ( int num: a ) System.out.print(num+" ");
    }

    /**
     * 尝试填充第 index 个商店的价格
     * @param index:第index个商店
     * @param val:价格
     * @return:是否已经完成填充
     */
    public static boolean dfs( int index, int val ) {
        // 没有记忆化就只有80分超时。
        if ( flag[index][a[index-1]][val] ) return false;
        // 标记以访问
        flag[index][a[index-1]][val] = true;
        a[index] = val;
        // 最后一步,判断最后一位是否成立
        if ( index == a.length-1 ) return (a[a.length-2]+a[a.length-1])/2 == b[b.length-1];
        // for循环遍历当前能枚举的最小点
        int st = b[index]*3 - a[index-1] - a[index], ed = st+2;
        for ( int nextCost = st; nextCost <= ed; nextCost++ )  {
            // 不存在负数的价格
            if ( nextCost <= 0 ) continue;
            if ( dfs(index+1, nextCost) ) return true;
        }
        return false;
    }

}

class Input {
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }
}

本文地址:https://blog.csdn.net/weixin_43732798/article/details/109583042

相关标签: CCF 题解