【题解】CF161B Discounts
2019-11-11 09:00:47来源:博客园 阅读 ()
【题解】CF161B Discounts
目录
- 题目
- 思路
- $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 %d\n",a[i].num);
}
printf("%d ",n-k+1);
for(int i=k;i<=n;++i) {
printf("%d ",a[i].num);
}
puts("");
return 0;
}
原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11836209.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash