解析

题目链接 题意很清晰了。

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

因此，由于凳子的打折情况最优就是给自己打折，那么我们将凳子按照价格排序，对于前 $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;
}