c/c++语言开发共享【题解】CF161B Discounts

题目

cf161b discounts

思路

贪心。很显然对于一个板凳（价格为c）所能使我们最多少花费$frac{c}{2}$的金钱。

原因如下：

• 如果你将一件价格比该板凳大的商品与板凳放在一起没有贡献。

• 如果你将一件价格比该板凳小的商品与板凳放在一起贡献减小。

贪心策略：将板凳中价格前$k-1$大的单独放一辆购物车，板凳不够就用商品即可。

$code$

#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #include<iomanip> #define min(a,b) a<b?a:b  inline void read(int &t) {     int x=0;bool f=0;char c=getchar();     while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}     t=f?-x:x; }  inline void write(int x) {     if(x<0) putchar('-'),write(-x);     else {         if(x/10) write(x/10);         putchar(x%10+'0');     } }  int n,k; struct dx {     int w,type,num;     friend bool operator <(dx x,dx y) {         if(x.type==y.type) return x.w>y.w;         return x.type<y.type;     }//板凳比其他商品的优先级要高，价格高的比价格低的优先级要高。 }a[1001];  int main() {     read(n),read(k);     for(int i=1;i<=n;++i) {         read(a[i].w),read(a[i].type);a[i].num=i;     }     std::sort(a+1,a+n+1);//排序,如此排序后将做法转化为了将k-1间商品单独放一辆购物车，剩余商品放入最后一辆购物车。      double cost=0;bool f=0;     int minn=0x7fffffff;      for(int i=1;i<=n;++i) {         if(i<=k-1) {             if(a[i].type==1) cost+=a[i].w*1.0/2.0;             else cost+=a[i].w*1.0;         }else {             cost+=a[i].w*1.0;             minn=min(minn,a[i].w);              if(a[i].type==1) f=1;//如果剩余商品中有个板凳的话要价格减半。          }     }     if(f) cost-=minn*1.0/2.0;     std::cout<<std::fixed<<std::setprecision(1)<<cost<<'n';//注意保留一位小数      for(int i=1;i<=k-1;++i) {         printf("1 %dn",a[i].num);     }     printf("%d ",n-k+1);     for(int i=k;i<=n;++i) {         printf("%d ",a[i].num);     }     puts("");     return 0; }