本文主要是介绍CodeForces - 338C Divisor Tree 【贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CodeForces - 338C
题意：
构造一颗树，使得包含给定的n个数，并且所有叶子节点为素数，每个节点等于所有子节点的积，求最少需要的节点数。
贪心思路：
每个数等于它子树上所有叶子节点的积，因此，使节点数最少就要使每个数公用尽可能多的叶子节点。将n个数从大到小排序，对每个数，每次选素因子最多的数作为子节点，直到不能选任何数为子节点为止。
实现代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
#include<list>
#include<bitset>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int prime[1000005],cnt;
ll a[10];
int n;
int used[10],ans;
int p_num[10];
int cmp(ll a,ll b) {return a>b;}
ll get(ll n)
{ll ret=0;for(int i=0;i<cnt&&(ll)prime[i]*prime[i]<=n;i++){while(n%prime[i]==0) ret++,n/=prime[i];}if(n>1) ret++;return ret;
}
void solve(int p)
{ll tmp=a[p];while(1){int j=-1;for(int k=p+1;k<n;k++){if(used[k]) continue;if(tmp%a[k]) continue;if(j==-1||p_num[k]>p_num[j]) j=k;}if(j==-1) break;used[j]=1;tmp/=a[j];if(p_num[j]>1) ans++;}if(!used[p]&&p_num[p]>1) ans+=p_num[p];
}
int main()
{cnt=0;memset(prime,0,sizeof prime);prime[1]=1;for(int i=2;i<1000005;i++){if(!prime[i]) prime[cnt++]=i;for(ll j=(ll)i*i;j<1000005;j+=i){prime[j]=1;}}while(~scanf("%d",&n)){memset(used,0,sizeof used);for(int i=0;i<n;i++)scanf("%I64d",&a[i]);sort(a,a+n,cmp);ans=0;int num=0;for(int i=0;i<n;i++)p_num[i]=get(a[i]);for(int i=0;i<n;i++){if(!used[i]){num++;ans++;}solve(i);}if(num>1) ans++;printf("%d\n",ans);}return 0;
}
这篇关于CodeForces - 338C Divisor Tree 【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
