/acm/contest/133/A
题意:就是给出一棵树,每个节点都有价值,问把所有节点都改成一种价值的最小花费,改一条边的两个节点所需的花费是两个节点的和。
方法:一开始想得是O(n*n)的算法,就是把所有点跑一遍,取小的,不用想,肯定TLE,然后优化,先统计输入数的和,那么第二个for就可以优化,变成O(n).
输入的数太大,不能用数组存来计算每个数出现的次数,怎么办?
用map来弄
数大,那就用去重后,这个数的位置代表这个数,mp储存的是这个数的位置
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=100005;map<ll,int>mp;ll a[maxn],c[maxn],v[maxn];int main(){int n,i,j,x,y,cnt,l;ll sum,minn,temp;scanf("%d",&n);sum=0;cnt=1;for(i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];if(mp.find(a[i])!=mp.end())//出现过{v[mp[a[i]]]++;}else{mp[a[i]]=cnt;//此数的位置v[cnt]=1;//此位置出现的次数,即是这个数出现的位置c[cnt]=a[i];//去重cnt++;}}for(i=1;i<=n-1;i++)scanf("%d%d",&x,&y);minn=sum-c[1]*v[1]+(n-(v[1]))*c[1];for(i=2;i<cnt;i++){temp=sum-c[i]*v[i]+(n-v[i])*c[i];minn=min(minn,temp);}printf("%lld\n",minn);}
如果觉得《染色(方法:要统计每个数出现的次数 而这个数很大 用数组存不了 怎么弄?)》对你有帮助,请点赞、收藏,并留下你的观点哦!