鏈接：https://www.nowcoder.com/acm/contest/133/A
來(lái)源：牛客網(wǎng)
?

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

題目描述

現(xiàn)在有一棵被Samsara-Karma染了k種顏色的樹(shù)，每種顏色有著不同的價(jià)值

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

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

現(xiàn)在，Applese的錢要用來(lái)買書(shū)(game)，所以他想要最小化代價(jià)

?

輸入描述:

輸入包括若干行 第一行包括一個(gè)數(shù)n，表示這棵樹(shù)有n個(gè)節(jié)點(diǎn) 第二行包括n個(gè)數(shù)，第i個(gè)數(shù)表示第i個(gè)節(jié)點(diǎn)的顏色coli **注意：一個(gè)顏色的標(biāo)號(hào)即價(jià)值

接下來(lái)的n - 1行，每行包括兩個(gè)數(shù)u, v，表示u節(jié)點(diǎn)與v節(jié)點(diǎn)之間有一條無(wú)向邊

n ≤ 100000, 1 ≤ coli ≤ 1e9，數(shù)據(jù)保證是一棵樹(shù)

輸出描述:

輸出包括一行 第一行包括一個(gè)數(shù)，表示最小代價(jià)

?

示例1

輸入

4 2 3 4 3 1 2 2 3 3 4

輸出

12

?

最開(kāi)始暴力過(guò)去的，數(shù)據(jù)比較弱。強(qiáng)行枚舉所有顏色的花費(fèi)。時(shí)間復(fù)雜度O(n^2)

#include <bits/stdc++.h> using namespace std; const int MAXN=1e5+10; int a[MAXN]; map<int, int >ma; set<int>se; int x[MAXN],y[MAXN]; int main() {int n;scanf("%d",&n);for (int i = 1; i <=n ; ++i) {scanf("%d",&a[i]);se.insert(a[i]);}for (int i = 1; i <n ; ++i) {scanf("%d%d",&x[i],&y[i]);}long long ans=1e14,sum=0;set<int>::iterator it;for (it=se.begin(); it !=se.end() ; ++it) {sum=0;for (int j = 1; j <=n ; ++j) {if((*it)!=a[j]) sum+=((*it)+a[j]);}ans=min(sum,ans);}printf("%lld\n",ans);return 0; }

思維：時(shí)間復(fù)雜度O(n)

#include<bits/stdc++.h> using namespace std; #define LL long longconst int MAXN = 1e5+10; const int INF = 0x3f3f3f3f; int n,u,v; int a[MAXN]; map<int,LL>mp,cost; int main(){while(scanf("%d",&n)!=EOF){LL sum = 0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);mp[a[i]] += a[i];sum += a[i];}for(int i=1;i<n;i++){scanf("%d%d",&u,&v);}LL ans = 1LL<<60;map<int,LL>::iterator it;for(it=mp.begin();it!=mp.end();it++){ans = min(ans,sum - it->second + (n - it->second / it->first) * it->first);}cout<<ans<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Wannafly挑战赛20 A 染色（暴力/思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。