讨论/《春招冲刺班 - 7 天刷题挑战》 - 最短移动距离/
《春招冲刺班 - 7 天刷题挑战》 - 最短移动距离
共 11 个回复

        对字节直播过程中的出现的代码的个人理解(闲着没事做,照着敲出来的,抄的时候有些地方抄错了,改用张同学提供的代码,列文虎克,哈哈哈哈),个人觉得真的非常难,如有不对,还请指正^_^
        之前一直做不出来,是因为考虑的时候存在一个问题,每次选择都是当前最近的(纯贪心,没有考虑全局信息),每个松鼠都是一个局部最优解,但这些松鼠的方案组合不一定为全局最优解,比如用例:
16 2
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
4 1
        如果采取后序+BFS,那么会造成4选2,1选16,但明显交换二者会得到更优的结果,对于其它几种树的遍历方式同样可以构造不符合纯贪心的用例出来

        由上述出现的问题,如果前后交换会更优,那么我们是否可以让后续选择的结点"间接"与前一个交换呢?这个间接实现是通过维护结点方向的路径代价来的,将一个路径拆分为"往上走"(即松鼠p到lca)和"往下走"(lca到最近的点now.S)两个部分,即:
        1.当前一个结点沿着某些结点往上走时,我们修正这些结点后续往下走的代价(减少),让当前方案的代价与交换选择方案后(更优)的代价相同
        2.当前一个节点沿着某些方向往下走时,我们修正这些结点后续往上走的代价(减少),让当前方案的代价与交换选择方案后(更优)的代价相同

        而这个往上或往下走的信息是记录在dir数组中的,具体细节看代码,有注释,这本质就是一个动态规划,真的很难想,代码有很多很有趣的细节,至少我这个业余的选手想不出来

#include <algorithm>
#include <cstdio>

using namespace std;

typedef pair<int, int> pii;
#define F first
#define S second

const int MAXN = 100005;
pii now, f[MAXN];
int c[MAXN], dir[MAXN];
int n, m, lca, ans;

inline int calc(int a, int b) {
    return a * b < 0 ? -1 : 1;
}

//
inline void update(int x) {
	//当前是否有房间 
    f[x] = c[x] ? pii(0, x) : pii(MAXN, MAXN);
	//左子结点
    int y = x * 2;
	//左边最近的房间,且目的地为f[y].S   路径长度为f[x].F(不一定真实存在,看f[y].F和S的取值)
    if (y <= n && f[y].F + calc(dir[y], 1) < f[x].F)
        f[x] = pii(f[y].F + calc(dir[y], 1), f[y].S);
	//右边最近的房间,且目的地为f[y].S   路径长度为f[x].F
    if (++y <= n && f[y].F + calc(dir[y], 1) < f[x].F)
        f[x] = pii(f[y].F + calc(dir[y], 1), f[y].S);
}

void query(int x, int ret) {
	//当前子树下面是否有房间,是否比当前最近的距离还小
    if (f[x].F + ret < now.F)
		//更新目标位置,lca记录最近公共祖先的位置
        lca = x, now = pii(f[x].F + ret, f[x].S);
	//判断是否往父节点方向是否更优
    if (x != 1)
        query(x / 2, ret + calc(dir[x], -1));
}

/*当x!=lca时 
修正1:当沿着某结点往上走时,需要修正后续沿着该点往下走的代价

修正lca到x之间的路径方向,即:如果前一个松鼠选择的路径是沿着x-->lca方向,即x到lca的中间的结点(含x,不含lca)都走父节点方向,当后一个松鼠的路径存在lca-->x方向中的某些连续边,即x-->lca(不含lca,且为前一个松鼠的路径方向)中的某些连续点,但此时方向与之前的方向是相反的,这些连续点是往子结点走,那么我们调整前后两次选择,会得到更优的结果

举例:
16 2
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
4 1
										松鼠1
								房间2      
						松鼠4
					8
			房间16
			
lca 为房间2
第一处(松鼠4)会先选择房间2,
第二处(松鼠1)会选择房间16,
如果不加修正,那么距离为1+4 =5
但更优的选择是:松鼠4 选房间16
				松鼠1 选房间2   总距离3
因此需要修正松鼠lca到4之间的路径代价,dir[4]--;由于update时,calc第二个参数为1,相乘为负,update后,此时松鼠4记录的最近距离和点分别为(1-1,16),即(0,16)
这样4(除左分支)的其他分支结点上的松鼠选择4左分支上的最近结点的路径代价需要变短,也就是调整策略,调换前后两个松鼠选择的房间(更优)

*/
void dec(int x) {
    update(x);
	//最近结点在当前子树下
    if (x == lca) return;
	//最近结点不在当前子树下,调整方向,往上走
    --dir[x];
    dec(x / 2);
}
/*
修正2:当沿着某结点往下走时,需要修正后续沿着该结点往上走的代价

记最近结点为now.S

当now.S不为lca时,即对于当前松鼠,是沿着lca-->now.S走的,即中间的结点都是往子节点走,修正now.S往lca方向走的路径代价,即如果后续某只松鼠存在now.S-->lca方向中的某些连续边,即lca--->now.S方向(前一松鼠路径方向)上的某些连续点,但此时这些点都是沿着父节点方向走,那么应该减少到目标的距离,即调换前后两次结果更优

举例:
								1
					松鼠2(1只)       房间3(1间)
				4				松鼠6(1只)
			8
	房间16
				
先为松鼠2找房间3,距离2
后为松鼠6找房间16,距离为6
但更优的是(2->16) 、(6->3)   3+1 = 4
修正3到1的之间方向:dir[3]++;使的松鼠6选择3上面分支的结点的距离减少

先修正往上走的代价,即经过3往上:
由于往父节点走calc第二个参数是-1,而dir[3]为正,calc返回-1,即往上走时,上面最近的点距离需要减少(即ret--),而松鼠6如果要选择1左分支下的房间,会经过6->3,距离减1,到达1时,距离为0(3-->1,距离加1(dir[1] = 0),同时1左分支下最近的房间的距离需要修正,按照修正1的方式即可,也就是0+1+1=2,这样就间接调整了前后两次选择
*/

void inc(int x) {
    update(x);
    if (x == lca) return;
    ++dir[x];
    inc(x / 2);
}

int main() {
    scanf("%d%d", &n, &m);
	//房间的数量
    for (int i = 1; i <= n; i++) scanf("%d", c + i);
	//初始化所有结点都往子节点走,f[x].F表示子节点有房间时,最近的距离   f[x].S表示最近的有房间结点的位置
    for (int i = n; i >= 1; i--) update(i);
    for (int i = 1; i <= m; i++) {
        int p;
        scanf("%d", &p);
        now = pii(MAXN, MAXN);
        query(p, 0);
		//加上最短的距离
        ans += now.F;
		//当前是往上走,修正后续往下走的代价
        dec(p);
		//选择的结点房间数量减一
        --c[now.S];
		//当前是往下走,修正后续往上走的代价
        inc(now.S);
        for (; p; p >>= 1) update(p);
    }
    printf("%d\n", ans);
    return 0;
}
13

1、计录每个节点到根节点的距离
2、记录每个节点到根节点的分支(左边或者右边,指大方向,根节点下,要么左边,要么右边)
3、对于处于该节点但是没有房间的松鼠重新寻找房间
遍历节点,分别计算有房间的节点到该松鼠所在节点的距离,取最小值
求解距离的方式:
如果处于不同的分支 则距离为 当前点到根 + 房间点到根
如果处同一分支,则距离为 当前点到根 - 公共根到根 + 房间点到根 - 公共根到根

看到这里辛苦了,通过测试用例 4/10,超出时间限制

1

感觉算法思路就是对于每个松鼠维护向下的最近的房间(也就是updateupdate函数),向上的最近房间(queryquery函数),这样就找出了距离其最近的房间,同时要保证路径不要交叉;如果路径出现交叉要减掉这部分,也就是一条边出现两条相反方向路径,那么就要减掉这个部分,这通过dec,incdec,inc函数维护。(代码就是下面HUST_DHC大佬那份,就不贴了)。个人理解,不知道对不对。

我看了下你的代码,也属于纯贪心的那种,且每次都为一个结点上的松鼠选择当前子树下合适的房间,忽略了父节点方向,但如果连父结点方向一并加入BFS搜索范围,会出现我之前提到的问题,子问题之间不存在严格的独立性,这个时候后续选择需要因为前面的选择做出动态调整,比如交换前后两次的选择

确实,主要是上课的时候,并没有很理解DP的思路,关于代价修正这里大佬可以指点下吗

代码问题最大的一点就是:对每个子树首先在子树下找房间,代码在bfs的时候,会排除父节点的方向,但是存在父方向的房间数足够,且路径更短的情况

8 1
1 0 0 0 0 0 0 1
2
可以试试这个样例

虽然听了课,但是对DP的思路并不是很理解,参考了理工唐同学的代码的以后给出java版可以通过的代码。如果有理解不对的地方请各位大佬指点

import java.util.*;
class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //初始化输入参数
        List<String[]>input = new ArrayList<>();
        int n=0,m=0;
        while(sc.hasNext()) input.add(sc.nextLine().split(" "));

        n = Integer.parseInt(input.get(0)[0]);
        m = Integer.parseInt(input.get(0)[1]);
        
        int [] treeRoom = new int [n+1];//每棵树上的房子数
        int [] mouse = new int [n+1];//每个树节点的松鼠个数
        int [] group = new int [n+1];//记录每个节点的父节点,与无向图联合使用
        //构建无向图
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int i=2;i<=n;i++){
            int root = i/2;
            group[i] = root;
            map.computeIfAbsent(root,v->new ArrayList<>()).add(i);
            map.computeIfAbsent(i,v->new ArrayList<>()).add(root);
        }
        //初始化树数组
        for(int i=1;i<=n;i++){
            treeRoom[i] = Integer.parseInt(input.get(1)[i-1]);
        }
        //初始化松鼠数组
        for(int i=0;i<m;i++){
            int node =  Integer.parseInt(input.get(2)[i]);
            mouse[node]++;;
        }
        Solution s = new Solution();
        System.out.print(s.getMinDistance(n,m,treeRoom,mouse,group,map));
    }
    long ans = 0;
    int [] treeRoom;
    int [] mouse;
    int [] group;
    int n;
    int m;
    Map<Integer,List<Integer>> map;
    /*
        方法主体,深搜每个节点,如果有松鼠就直接分配了,将多余的老鼠返回给父节点进行分配,子树内安排不了就往上走
    */
    public long getMinDistance(int n,int m,int []treeRoom,int []mouse,int[] group,Map<Integer,List<Integer>> map){
        this.treeRoom = treeRoom;
        this.mouse = mouse;
        this.group = group;
        this.n = n;
        this.m = m;
        this.map = map;
        dfs(1,-1);
        return ans;
    }
    public void dfs(int curr,int pre){
        //深搜
        for(Integer neig:map.get(curr)){
            if(pre==neig)   continue;  
            dfs(neig,curr);
        }
        //多余的松鼠交给父节点
        for(Integer neig:map.get(curr)){
            if(neig == pre) continue;
            mouse[curr]+=mouse[neig];
            ans += mouse[neig];
        }
        //广搜在子树内安排
        bfs(curr);
    }
    private void bfs(int node){
        Deque<int[]>queue = new ArrayDeque<>();
        queue.add(new int []{node,0});
        while(!queue.isEmpty()){
            int [] curr = queue.poll();
            int n = curr[0],dist = curr[1];
            if(mouse[node]==0) break;//给定的节点没松鼠了就提前跳出
            if(treeRoom[n]!=0){
                int num = Math.min(mouse[node],treeRoom[n]);   //分配数量为房间数与松鼠数中的较小值
                mouse[node] -= num;
                treeRoom[n] -= num;
                ans += (long)dist * (long)num;
            }
            for(Integer neig : map.get(n)) {
                if(neig == group[n]) continue;
                queue.push(new int[]{neig,dist+1});
            }
        }
    }
}

应是松鼠和房间的最近公共祖先到根节点的距离,但是这个时间复杂度很高,数据规模100000,最多支持O(NlogN)的算法

请问一下 公共根到根 什么意思