题意翻译

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

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

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

输入格式

第一行两个整数、；

第行至第行，每行两个整数， 。

其中表示商品的价格，表示商品的类型（表示它是凳子，表示它不是凳子）

输出格式

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

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

后面跟着$$，分别表示商品的编号。

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

Input & Output 's examples

Input 's eg 1

3 2
2 1
3 2
3 1

Output 's eg 1

5.5
2 1 2
1 3

Input 's eg 2

4 3
4 1
1 2
2 2
3 2

Output 's eg 2

8.0
1 1
2 4 2
1 3

样例解释

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

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

数据范围和约定

对于的数据，

分析

又是一道贪心好题

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

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

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

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

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

剩下的见代码注释。

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;
}

THE END