鏈接：https://www.nowcoder.com/acm/contest/133/A
來源：牛客網
?

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

現在有一棵被Samsara-Karma染了k種顏色的樹，每種顏色有著不同的價值

Applese覺得Samsara-Karma染的太難看了，于是打算把整棵樹重新染成同一種顏色

但是，由于一些奧妙重重的原因，每一次染色Applese可以選擇兩個有邊相連的點，將其中一個染成另一個的顏色。而進行一次這樣的操作需要付出兩種顏色價值和的代價

現在，Applese的錢要用來買書(game)，所以他想要最小化代價

?

輸入描述:

輸入包括若干行 第一行包括一個數n，表示這棵樹有n個節點 第二行包括n個數，第i個數表示第i個節點的顏色coli **注意：一個顏色的標號即價值

接下來的n - 1行，每行包括兩個數u, v，表示u節點與v節點之間有一條無向邊

n ≤ 100000, 1 ≤ coli ≤ 1e9，數據保證是一棵樹

輸出描述:

輸出包括一行 第一行包括一個數，表示最小代價

示例1

輸入

復制

4 2 3 4 3 1 2 2 3 3 4

輸出

復制

12 #include<cstdio> #include<algorithm> #include<map> using namespace std; const int maxn = 1e5 + 100; int c[maxn]; map<long long ,long long >mp; int main() { //freopen("C://input.txt","r",stdin); int n;long long int t=0x3f3f3f3f3f3f3f3f;long long int sum=0;scanf("%d",&n);for(int i=1;i<=n;i++){int m;scanf("%d",&m);sum+=m;mp[m]++;}for(map<long long ,long long >::iterator it=mp.begin();it!=mp.end();it++){t=min(t,sum-(it->first * it->second)+ (it->first*(n-it->second)));}printf("%lld\n",t);return 0; }

公式 某個點的總花費=總和 - ?自身值*自身點出現的次數 ?+ 自身值*其他點的個數 ?（自己推一下）

這里用map用來記錄一個點出現的次數。

舉個例子 ?mp[m]++； ?迭代器 ?it ->first=m （即m自身的值） ?it->second 代表mp[m]（即m出現的次數）

map迭代器 it是一個指針，用 ?‘->’來指向

注意 ?vector 的迭代器 it ?可以直接用 *it ?來代表其內容

一開始想用結構體 離散化來做，才發現數據范圍1e9，數組開不到，只能用map。

總結

以上是生活随笔為你收集整理的牛客网 Wannafly挑战赛20 A-染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。