题解 CF161B 【Discounts】

原题传送门

首先讲一下看这一篇题解的好处

1. 题解区较多题解是分点作答，本篇为同时求解
2. 思路清晰，变量名指向明显
3. 讲解明白，码量较小且码风好看

首先我的代码比较这篇声称“本题最短题解”的代码，正确性可以保证。至于这位作者的AC代码，是抄袭这一篇的，至于他说的：“读者自证不难”，我认为纯属是因为不会。

观点仅代表个人观点，希望管理员大大可以撤下该篇题解。由于我只发现这人抄袭这一篇，无法对其进行举报。

以上吐槽是因为我最烦那种省略重点部分的题解。

正片开始

我们希望尽量省钱，所以尽量每个购物车都有凳子。

那么先想购物车中有凳子的情况。

1. 现在车里这个凳子最便宜，那么省下这个凳子一半的钱；
2. 现在车里有比这个凳子便宜的东西，那么省下不到这个凳子一半的钱（最便宜的东西的半价）。

观察以上两种情况可知，把凳子单独放一辆车一定最优。商家只是想促销凳子。

最终，一种可行的最优购买方案是将最贵的k-1个 (或全部，比如当凳子不够时) 凳子单独放，剩下的购物车放其余的所有物品。

时间复杂度为排序的复杂度\text{O(nlogn)}，对于不是凳子的物品可以不排序优化常数，但是并不会对总复杂度产生影响。

细节处理会放在代码注释。

Code

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

using namespace std;

int n,k,tot,cnt,p[1010][1010];
double ans;
struct node {int id; double v;} chair[1010],sold[1010];//tot:chair cnt:not chair
bool cmp(const node &a,const node &b) {return a.v < b.v;}//从大到小排序

int main()
{
//  freopen("work.in","r",stdin); freopen("my.out","w",stdout);
    scanf("%d%d",&n,&k);
    double c;
    for(int i=1,t;i<=n;i++)
    {
        scanf("%lf%d",&c,&t);//分别处理
        if(t == 1) chair[++tot]=(node) {i,c};
        else sold[++cnt]=(node) {i,c};
    }
    sort(chair+1,chair+1+tot,cmp);
    sort(sold+1,sold+1+cnt,cmp);
    int num=tot;
    for(int i=1;i<k && i<=num;i++) {ans+=chair[tot].v*1.0/2.0; p[i][++p[i][0]]=chair[tot--].id;}
    if(num >= k)//装得完k-1
    {//注意这里的!cnt，如果不加的话，结构体内变量有可能初始为0导致答案偏差
        if(!cnt || chair[1].v < sold[1].v) chair[1].v*=1.0/2.0;//不止k-1个凳子的情况可以合并处理
        else sold[1].v*=1.0/2.0;//半价
        for(int i=1;i<=tot;i++) {ans+=chair[i].v; p[k][++p[k][0]]=chair[i].id;}//这里的p数组是第二问的答案数组
        for(int i=1;i<=cnt;i++) {ans+=sold[i].v; p[k][++p[k][0]]=sold[i].id;}//加上剩下的
    }
    else//装不满k-1个
    {
        for(int i=num+1;i<k;i++) {ans+=sold[cnt].v; p[i][++p[i][0]]=sold[cnt--].id;}
        for(int i=1;i<=cnt;i++) {ans+=sold[i].v; p[k][++p[k][0]]=sold[i].id;}
    }
    printf("%.1lf",ans);
    for(int i=1;i<=k;i++)
    {
        printf("\n%d",p[i][0]);
        for(int j=1;j<=p[i][0];j++) printf(" %d",p[i][j]);
    }//输出
//  fclose(stdin); fclose(stdout);
    return 0;
}

\text{Thank you for your reading!}

您的点赞和评论是对作者最大的支持！点个赞再走嘛。