題目
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.uj5u.com/houduan/88001.html
標籤：C++
上一篇：Run-Time Check Failure #0 - The value of ESP was not properly saved across a function call錯誤
下一篇：C/C++ 的編譯和鏈接