小欧吃苹果 - OPPO 2024 校招正式批次笔试试题--数据开发（C 卷）

在处理这个问题前，先看一个经典的贪心算法题目。信息学奥赛一本通（C++版）在线评测系统http://ybt.ssoier.cn:8088/problem_show.php?pid=1320

注意移动纸牌的贪心策略并不是题目中给出的移动次序：第1堆纸牌9<10，因为是最左侧，它只能从第2堆移动过来一张，这个动作是必须做的（没有别的选择），移动1次。第2堆现在7张，只能从第3堆移动过来3张，移动2次。第3堆14张，只能往第4堆移动4张，移动3次。第四堆恰好10张，不移动。此类问题算法从边界节点处理（当然也可以从第n堆开始逆向处理），因为边界只有唯一的移动选择。

题目分析：回到本题目，树中每个节点都有苹果数量的要求，在贪心算法处理过程中，只需先处理哪些只有唯一处理方案的节点，采用类似拓扑排序的方法即可求解。如题目中样例。

拓扑排序针对是有向无环图度为0的点，无向图如何拓扑排序呢？从上图观察可以发现无向图中边缘点度为1。因此将拓扑排序处理节点判定条件从度为0改为度为1即可。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,a[100005],v[100005],d[100005],ans=0;
vector<int>e[100055];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,x,y;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<n;i++)/**< 无向图存储 */
    {
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
        d[x]++,d[y]++;/**< 统计度 */
    }
    queue<int>q;
    for(i=1;i<=n;i++)
        if(d[i]==1) q.push(i);
    while(q.size())
    {
        x=q.front();
        v[x]=1;/**< 标记为已处理节点 */
        q.pop();
        for(i=0;i<e[x].size();i++)/**< x所有邻接点，树结构实际只有一个点可以起作用 */
        {
            y=e[x][i];
            if(v[y]==0)/**< 只能和没有处理过节点交换苹果 */
            {
                ans+=abs(x-a[x]);/**< x节点将自己的值处理为x，花费代价是abs(x-a[x]) */
                if(x>=a[x])  /**< x上多出的值或者缺少的值只能传递给y */
                    a[y]-=x-a[x];
                else
                    a[y]+=a[x]-x;
                d[y]--;/**< y的度减一 */
                if(d[y]==1)
                    q.push(y);
            }
        }
    }
    cout<<ans;
    return 0;
}