贪心合集

December 06, 2020 1954

【1】牛客：装进肚子

题目描述：

自从ZZZZone吃完糖果后，他开始改吃巧克力了，他每天想吃n个巧克力增在甜蜜值，他决定早上吃K个巧克力，晚上吃n - K个巧克力，每个巧克力在早上吃和在晚上吃的甜蜜值是不一样的，他想让自己得到的甜蜜值最大，并想知道最大是多少。请你编程帮助他。

输入描述：

第一行包含两个数n，K表示每天要吃的巧克力数量和要在早上吃的数量。（n <= 100000, K <= n)
第二行包含n个整数Ai（1 <= i <= n) 表示个第i个巧克力在早上吃可得到的甜蜜值 (Ai <= 100000)
第三行包含n个整数Bi（1 <= i <= n) 表示个第i个巧克力在晚上吃可得到的甜蜜值 (Bi <= 100000)

输出描述：

输出仅一行包含一个整数表示ZZZZone能获得的最大甜蜜值。

输入：

2 1
3 6
2 8

输出：

11

思路：

假设每一块都是早上吃，那么要拿一块来晚上吃就需要-a[i]+b[i]，即为b[i]-a[i],那么对b[i]-a[i]由大到小排序，前n-k个就是晚上需要吃掉的糖果了。

AC代码：

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
27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*结构体排序*/
struct sug{
    ll day,nit;
}sugs[100100];
bool cmp1(sug a,sug b){
    return (a.day-a.nit)>(b.day-b.nit);
}
int main(){
    ll n,k,ans;
    ans=0;
    scanf("%lld%lld",&n,&k);
    for(ll i=0;i<n;i++){
        scanf("%lld %lld",&sugs[i].day,&sugs[i].nit);
    }
    sort(sugs,sugs+n,cmp1);
    for(ll i=0;i<k;i++){
            ans+=sugs[i].day;
    }
    for(ll i=k;i<n;i++){
        ans+=sugs[i].nit;
    }
    printf("%lld\n",ans);
    return 0;
}

感谢我zser大佬的讲解～

【2】牛客：合并石子

思路：

灰常简单的一个题，不过刚开始被我想复杂了，其实就是要留下最大的，拿最大的跟其他的数相加，最后列出样例的算式为：(5+1)+(5+3)+(5+5)+(5+2)=31，假设max为最大的数，sum为所以数的和，即为max*(n-2)+sum；

AC代码：

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
#include  "stdio.h"
#include  "iostream"
#include <string.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll maxx=0;
int main()
{
    cin>>n;
    ll sum=0;
    ll ans=0;
    for(ll i=0;i<n;i++){
        cin>>m;
        sum+=m;
        if(m>maxx){
            maxx=m;
        }
    }
    /*cout<<"sum="<<sum<<endl;
    cout<<"maxx="<<maxx<<endl;*/
    ans=maxx*(n-2)+sum;
    cout<<ans<<endl;
    return 0;
}
  • 本文作者：lybbor
  • 版权声明：本博客所有文章均采用 BY-NC-SA 许可协议，转载请注明出处！