目录
- $code$
题目
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600989.html