3 2 2 1 3 2 3 1
5.5 2 1 2 1 3
4 3 4 1 1 2 2 2 3 2
8.0 1 1 2 4 2 1 3

按照大小排下序,你会发现,如果按照从大到小的顺序,那么给凳子打折一定是最优的

于是,我们就可以找凳子打折,最后无论剩下多少都撂倒最后一个购物车里

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 1200 #define rep(x,y,z) for(int x = y ; x <= z ; x ++) using namespace std ; struct dy{ int c , t , id ; }a[maxn] ; int n , m , l , pos , num , sum , res , g[maxn] , s[maxn] , ans[maxn][maxn] , k; bool book[maxn] ; double money ; int cmp(dy x , dy y) { return x.c > y.c ; } int main() { scanf("%d%d",&n,&k) ; rep(i,1,n) { a[i].id = i ; scanf("%d%d",&a[i].c,&a[i].t) ; if(a[i].t == 1) res ++ ; }sort(a+1,a+1+n,cmp) ; rep(i,1,n) { if(k > 1 && a[i].t == 1) { k -- ; res -- ; book[i] = 1 ; ans[++num][++s[num]] = a[i].id ; money += 0.5*double(a[i].c) ; if(!res) break ; } } if(res) { rep(i,1,n) { if(book[i]) continue ; pos = i ; g[++sum] = a[i].id ; money += double(a[i].c) ; } money -= 0.5*double(a[pos].c) ; }else { rep(i,1,n) { if(book[i]) continue ; if(k > 1) { k -- ; ans[++num][++s[num]] = a[i].id ; money += double(a[i].c) ; }else { g[++sum] = a[i].id ; money += double(a[i].c) ; } } } printf("%.1lf\n",money) ; rep(i,1,num) { printf("%d ",s[i]) ; rep(j,1,s[i]-1) { printf("%d ",ans[i][j]) ; }printf("%d\n",ans[i][s[i]]) ; } if(!sum) return 0 ; printf("%d " , sum ) ; rep(i,1,sum-1) { printf("%d ",g[i]) ; }printf("%d\n",g[sum]) ; return 0 ; }