SDUT 3923 打字 （贪心）

Problem Description

snow 是个热爱打字的家伙，每次敲出更快的速度都会让他很开心。现在，他拿到一篇新的打字文章，已知这篇文章只有 26 个小写英文字母，给出 snow 打出这 26 个英文字母分别需要多少时间 (s)，问 snow 打完这篇文章获得的 kpm（打正确的字数/所花的分钟数）最大为多少？

注意 snow 可能会打错一些字哦。打错的必定是文章里面存在的。

Input

多组输入。

对于每组数据，首先输入 26 个整数，分别表示打出 a, b, c, …, z 这 26 个字母需要的时间（保证是 int 范围内的正整数），然后给出一个字符串，长度不超过 1000，保证只包含小写英文字母。

Output

对于每组数据，输出一行，表示最大的 kpm，保留 2 位小数。

Example Input

1 2 2 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abcd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abcd

Example Output

40.00
25.71

思路

记得同步赛的时候题目中一开始没有 打错的必定是文章里面存在的。 这一句的，然后无辜的 WA 了。

总之题面改过好多次，也比较难懂（可能是描述有问题吧）

打字时我们有可能会使用文章中时间最短的字母来代替一个时间比较长的字母然后敲错。

于是，一开始我们可以根据时间把文章内容排序，并且记录其中花时最少的时间。

然后设定枚举变量 i 代表 敲对的字符数-1 ，然后此时的花时便是 sum+(len-i-1) × minn ，计算找最大值即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f
double p[30],minn;
int s[1100];

bool cmp(const int &a,const int &b)
{
    return p[a]<p[b];
}

void solve(int len)
{
    double ans=0.0,sum=0.0;
    for(int i=0; i<len; i++)
    {
        sum+=p[s[i]];
        ans=max(ans,double(i+1)/(sum+double(len-i-1)*minn));
    }
    printf("%.2lf\n",ans*60.0);
}

int main()
{
    while(cin>>p[0])
    {
        //minn=p[0];
        for(int i=1; i<26; i++)
        {
            cin>>p[i];
            //minn=min(minn,p[i]);
        }
        string st;
        cin>>st;
        int len=st.length();
        minn=INF;
        for(int i=0; i<len; i++)
        {
            s[i]=st[i]-'a';
            minn=min(minn,p[s[i]]);
        }
        sort(s,s+len,cmp);
        solve(len);
    }
    return 0;
}