【bzoj2697】特技飞行

最新推荐文章于 2019-01-08 08:36:08 发布

黑猫black

最新推荐文章于 2019-01-08 08:36:08 发布

阅读量327

点赞数

分类专栏：贪心

本文链接：https://blog.csdn.net/zhaoyh2000/article/details/54866643

版权

贪心专栏收录该内容

2 篇文章

订阅专栏

本文介绍了一种简单的贪心算法应用实例——洗发水特技问题。通过将高价值特技放置于序列两端以获取最大收益，文章详细阐述了算法实现过程，并提供了完整的C++代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

我的洗发水，特级特技加特技23333
比较简单的贪心，我们可以发现只要在开头加过一遍特技就可以一直获得收益（只要在结束的时候再加一遍），所以为了获得尽可能多的收益，我们将价值大的特技尽可能放在两边，贪心的正确性其实是很显然的（废话，显不显然我都是不会证明的）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;
const int N=1010;
int c[N],ans,n,k;
inline int F()
{
    register int aa,bb;register char ch;
    while (ch=getchar(),(ch<'0'||ch>'9'));aa=ch-'0';
    while (ch=getchar(),ch<='9'&&ch>='0')aa=(aa<<3)+(aa<<1)+ch-'0';return aa;
}
bool cmp(const int &a,const int &b){return a>b;} 
int main()
{
    cin>>n>>k;
    for (int i=1;i<=k;i++)
    c[i]=F();
    sort(c+1,c+k+1,cmp);
    k=min(k,n/2);
    n--;
    ans=0;
    for (int i=1;i<=k;i++)
    {
        ans+=n*c[i];
        n-=2;
    }
    cout<<ans;
 }