cf 12C Fruits（贪心【简单数学】）

题意：

m个水果，n个价格。每种水果只有一个价格。

问如果给每种水果分配价格，使得买的m个水果总价格最小、最大。

输出最小值和最大值。

思路：

贪心。

代码：

bool cmp(int a,int b){
    return a>b;
}

string name;
map<string,int> mp;
int price[200],fruit[200];
int cn;
int n,m;


int main(){

    cin>>n>>m;

    mp.clear();
    cn=0;
    mem(fruit,0);
    mem(price,0);

    rep(i,1,n) scanf("%d",&price[i]);
    rep(i,1,m){
        cin>>name;
        if(mp[name]==0){
            fruit[++cn]=1;
            mp[name]=cn;
        }
        else{
            fruit[mp[name]]++;
        }
    }
    sort(price+1,price+1+n);
    sort(fruit+1,fruit+1+cn,cmp);
    ll ans1=0;
    ll ans2=0;
    rep(i,1,cn){
        ans1+=((ll)1*price[i]*fruit[i]);

    }
    sort(price+1,price+1+n,cmp);
    rep(i,1,cn){
        ans2+=((ll)1*price[i]*fruit[i]);
    }
    printf("%I64d %I64d
",ans1,ans2);

    return 0;
}