51node 1182 完美字符串

Posted by kele on July 15, 2018

51nod 1182 完美字符串

超级简单的贪心算法
首先将n个字符按照字符个数进行排序,尽可能让完美度最大的话,就是让字符个数多的得到较大的完美度,就可以得到最后的最大完美度了

最优子结构:

贪心选择:
尽可能给字符个数较多的字符较大的完美度

#include <iostream>
#include<stdio.h>
#include<string>

using namespace std;

void  insert_array(int a[])
{
    int tmp=0;
    for(int i=1; i<26; i++)
    {
        int j=i;
        while(j>0&&a[j]>a[j-1])
        {
            tmp=a[j];
            a[j]=a[j-1];
            a[j-1]=tmp;
            j--;
        }
    }
}


int main()
{
    char s[10005];
    scanf("%s",s);
    int temp[26];
    for(int i=0; i<26; i++)
        temp[i]=0;
    for(int i=0; s[i]!='\0'; i++)
    {
        if(s[i]-97>=0)
            temp[s[i]-97]++;
        else  if(s[i]-65>=0)
            temp[s[i]-65]++;

    }
    insert_array(temp);
    int sum=0;
    for(int i=26; i>=0; i--)
    {
        if(temp[26-i]>0)
            sum+=temp[26-i]*i;
        else
        {
            while(temp[i]==0)
                i--;
        }
    }
    cout<<sum<<endl;

}