CF161B Discounts 题解

解析

题目链接 题意很清晰了。

我们考虑凳子的折扣情况。由于凳子本身也是一个物品,那么如果存在一个比凳子贵的物品在购物车中,那么打折的是凳子,如果有一个比凳子便宜的物品在购物车中——那还不如给凳子打折呢!合着这个商场就是给凳子打折而已。

因此,由于凳子的打折情况最优就是给自己打折,那么我们将凳子按照价格排序,对于前 $k-1$ 辆购物车,每辆购物车都放一辆凳子,然后剩下的东西全塞最后一辆车里。

在凳子不够的时候再特判一下就好了,详见代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
struct node{
    int c,t,id;
}a[N];
int n,k,cnt;
double ans;
inline bool cmp(node i,node j){//先类型,再单价
    if(i.t!=j.t) return i.t<j.t;
    return i.c>j.c;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i].c,&a[i].t);
        a[i].id=i;
        if(a[i].t==1) cnt++;
        ans+=a[i].c;
    }
    sort(a+1,a+1+n,cmp);
    if(cnt>=k-1){//凳子够前 k-1 辆车
        for(int i=1;i<=k-1;i++) ans-=0.5*a[i].c;
        if(cnt>=k)//够不够最后一辆车
            ans-=min(a[cnt].c,a[n].c)*0.5;//凳子和其他商品中最便宜的一个也要打折
    }
    else{//凳子不够
        for(int i=1;i<=cnt;i++){
            ans-=0.5*a[i].c;
        }
    }
    printf("%.1lf\n",ans);
    for(int i=1;i<=k-1;i++){
        printf("1 %d\n",a[i].id);
    }
    printf("%d ",n-k+1);
    for(int i=k;i<=n;i++)
        printf("%d ",a[i].id);
    return 0;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇