题目大意
给你N本书,每本书由一个厚度t[i](1或者2),宽度w[i],高度都是一样,把一些书竖着放,然后一些书横着放在同一层,就像下图那样放:
问你把所有的书放好之后竖着的书的总厚度是多少?
题解
题目有个重要条件,那就是每本书的厚度要么为1要么为2,因此我们可以根据书的厚度分为两类,然后每类按书的宽度从大到小排序,然后用二重循环进行枚举,把厚度为1的前i个和厚度为2的前j个竖着放,其他的横着放,在横着放的总宽度不超过竖着放的总厚度的前提下,求出一个竖着放总厚度最小的值来,这就是最终答案,为什么可以这样贪心呢?因为竖着放的书是不用考虑宽度的,而横着放的是考虑宽度的,所以我们肯定是把宽度小的横着放~~~
代码:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define MAXN 105 #define INF 0x3f3f3f3f typedef struct { int x,y; }NODE; NODE a[MAXN],b[MAXN]; int suma[MAXN],sumb[MAXN]; bool cmp(NODE a,NODE b) { return a.y>b.y; } int main() { int n,ta=0,tb=0; scanf("%d",&n); for(int i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); if(x==1) a[++ta].x=x,a[ta].y=y; else b[++tb].x=x,b[tb].y=y; } sort(a+1,a+ta+1,cmp); sort(b+1,b+tb+1,cmp); for(int i=1;i<=ta;i++) suma[i]=suma[i-1]+a[i].y; for(int i=1;i<=tb;i++) sumb[i]=sumb[i-1]+b[i].y; int ans=INF; for(int i=0;i<=ta;i++) for(int j=0;j<=tb;j++) { int tik=i+2*j,w=suma[ta]-suma[i]+sumb[tb]-sumb[j]; if(w<=tik&&tik<ans) ans=tik; } printf("%d ",ans); return 0; }