题意翻译

超市进行优惠活动，顾客如果在一架购物车中放上一个凳子$(?)$，他就可以半价买掉这架购物车里最便宜的商品。

每一辆购物车的容量是无限的，但一个购物车里只能有一件商品半价。

现在$Polycarpus$要用$k$架购物车装要买的$n$件商品，里面有一些是凳子。他希望用最少的钱来买这些东西。

输入格式

第一行两个整数$n$、$k$；

第$2$行至第$n+1$行，每行两个整数$c_i$，$t_i$ 。

其中$c_i$表示商品$i$的价格，$t_i$表示商品$i$的类型（$1$表示它是凳子，$2$表示它不是凳子）

输出格式

第一行输出一个一位小数，表示折扣之后最少需要付的价格。

接下来的$k$行，每行开头输出一个整数$a_i$，表示购物车$i$中商品的数量。

后面跟着 $a_i$ 个整数 $b_1,b_2...b_{a_i}$ ，分别表示商品的编号。

方案可能有很多，输出其中一种即可。购物车和商品的输出顺序不作要求。

Input & Output ‘s examples

Input ‘s eg 1

Output ‘s eg 1

5.5
2 1 2
1 3

Input ‘s eg 2

Output ‘s eg 2

样例解释

在样例$1$中，购物车有$2$架，其中一架装商品$1$（凳子）和$2$（其他），另一架装商品$3$（凳子）。

这样安排便可以使价格最低。

数据范围和约定

对于$100\%$的数据，$1 < n , k < 10^3 ， 1 < c_i < 10^9 ， t_i \in \lbrace 1 , 2 \rbrace$

分析

又是一道贪心好题

我们先只考虑单个凳子的情况，显然，一个凳子只能让自己或者一个价格比自己低的东西半价。

而题目中让我们最小化价格，即让省下的钱最多。因此，我们尽量多的让一个凳子单独在一个购物车中。

显然，这个最大值为$k - 1$。因为你还要留出一辆购物车来存储其他的物品。

但这还不够。如果凳子的数量小于$k - 1$的话，我们就把所有的凳子半价，然后原价买下其他商品即可

最后别忘了保留一位小数。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

int n , k;

struct Node{
    long double val;    //题目要求输出一位小数，因此要开long double
    int num;
    int str;
}node[N];

int cnt;
long double ans_num;

bool cmp(Node a , Node b){      
    if(a.str == b.str == 1){       //如果他们都是凳子，就把价值大的放在前边。
        return a.val > b.val;
    }                           
    else{                       //否则，将凳子放在前边
        return a.str < b.str;
    }
}

pair<int  , int > ans[N];

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> node[i].val >> node[i].str;
        node[i].val *= 1.0;
        node[i].num = i;
        if(node[i].str == 1){
            cnt ++;     //记录凳子的数量
        }
    }
    sort(node + 1 , node + 1 + n , cmp);
    if(cnt > k - 1){        //分类讨论，当凳子数量大于购物车数量-1时
        for(int i = 1; i <= k - 1; i ++){
            node[i].val /= 2;
            ans_num += node[i].val;
            ans[i] = make_pair(1 , node[i].num);
        }
        long double minn = 0x3f3f3f3f;
        for(int i = k; i <= n; i ++){
            ans_num += node[i].val;
            if(node[i].val < minn){
                minn = node[i].val;
            }
        }
        ans_num -= minn;
        ans_num += minn / 2;
        cout << fixed << setprecision(1) << ans_num << "\n";
        for(int i = 1; i <= k - 1; i ++){
            cout << ans[i].first << " " << ans[i].second << "\n";
        }
        cout << n - k + 1 << " ";
        for(int i = k; i <= n; i ++){
            cout << node[i].num << " ";
        }
        puts("");
    }
    else if(cnt == k - 1){  //当凳子数量等于购物车数量-1时
        for(int i = 1; i <= k - 1; i ++){
            node[i].val /= 2;
            ans_num += node[i].val;
            ans[i] = make_pair(1 , node[i].num);
        }
        for(int i = k; i <= n; i ++){
            ans_num += node[i].val;
        }
        cout << fixed << setprecision(1) << ans_num << "\n";
        for(int i = 1; i <= k - 1; i ++){
            cout << ans[i].first << " " << ans[i].second << "\n";
        }
        cout << n - k + 1 << " ";
        for(int i = k; i <= n; i ++){
            cout << node[i].num << " ";
        }
        puts("");
    }
    else{   //当凳子数量小于购物车数量-1时
        for(int i = 1; i <= cnt; i ++){
            node[i].val /= 2;
            ans_num += node[i].val;
            ans[i] = make_pair(1 , node[i].num);
        }
        for(int i = cnt + 1; i <= n; i ++){
            ans_num += node[i].val;
        }
        cout << fixed << setprecision(1) << ans_num << "\n";
        for(int i = 1; i <= cnt; i ++){
            cout << ans[i].first << " " << ans[i].second << "\n";
        }
        for(int i = cnt + 1; i <= k - 1; i ++){
            cout << 1 << " " << node[i].num << "\n";
        }
        cout << n - k + 1 << " ";
        for(int i = k; i <= n; i ++){
            cout << node[i].num << " ";
        }
        puts("");
    }
    return 0;
}