题目链接：http://codeforces.com/contest/161/problem/B
题意：
有n个商品和k辆购物车，给出每个商品的价钱c和类别t（1表示凳子，2表示铅笔），如果一辆购物车中有凳子，那么这辆购物车中最便宜的那个物品的价格能减少50%，问你如何放这些物品才能使总价钱最少。
思路：
简单贪心，判断凳子数量是否大于等于k行。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, int> P;
const int N = ;
LL a[N];
P val[N], val2[N];
LL inf = 1e9 + ;
vector <int> res[N];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
int pos = , pos2 = , c;
for(int i = ; i <= n; ++i) {
scanf("%lld %d", a + i, &c);
if(c == ) {
val2[++pos2].first = a[i];
val2[pos2].second = i;
} else {
val[++pos].first = a[i];
val[pos].second = i;
}
}
sort(val + , val + pos + );
sort(val2 + , val2 + pos2 + );
double ans = ;
int f = ;
if(pos >= m) {
int i, j;
for(i = pos, j = m - ; j; --i, --j) {
ans += val[i].first * 1.0 / ;
res[++f].push_back(val[i].second);
}
++f;
for(; i >= ; --i) {
ans += val[i].first;
res[f].push_back(val[i].second);
}
for(i = pos2; i > ; --i) {
ans += val2[i].first;
res[f].push_back(val2[i].second);
}
if((val[].first >= val2[].first && pos2)) {
ans += val[].first;
ans += val2[].first*1.0 / ;
res[f].push_back(val[].second);
res[f].push_back(val2[].second);
} else if(pos2) {
ans += val2[].first;
ans += val[].first*1.0 / ;
res[f].push_back(val2[].second);
res[f].push_back(val[].second);
} else {
ans += val[].first*1.0 / ;
res[f].push_back(val[].second);
}
} else {
for(int i = pos; i; --i) {
ans += val[i].first * 1.0 / ;
res[++f].push_back(val[i].second);
}
int i, j;
for(i = pos2, j = pos + ; i && j <= m; --i, ++j) {
ans += val2[i].first;
res[++f].push_back(val2[i].second);
}
for(; i; --i) {
ans += val2[i].first;
res[f].push_back(val2[i].second);
}
}
printf("%.1f\n", ans);
for(int i = ; i <= m; ++i) {
printf("%d ", res[i].size());
for(int j = ; j < res[i].size(); ++j) {
printf("%d%c", res[i][j], j == res[i].size() - ? '\n': ' ');
}
}
return ;
}