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认证解题目录
题目
思路过程
给的是第二天的菜价,求的是第一天字典序最小的菜价,假设第一天的菜价为 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