B. Ordering Pizza(思维,贪心)

本以为这题会是个大模拟,哎,我太笨了

$吃a大于吃b的人我们倾向于让他吃a,否则吃b$

$但是这里要是完全按照这个规则可能最后买的披萨不是最小的$

$把人分成两类,a>b和a<=b的$

$在某类人的内部,设他们能吃x片披萨$

$如果x能整除S(每个披萨的片数),那肯定都买这类,因为不会浪费$

$否则买x/S个这种披萨,余一些$

$另一类人也这样余一些$

当总共剩余的人大于S,无论如何都要买2个披萨,那不如买两种

否则,只买一类披萨,模拟一下即可

/*
买q*s块1,w*s块2 
就按照b-a来排序,越在前面的优先吃b 
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
struct p{int s,a,b;
};
bool maxa(p q,p w){return q.a-q.b<w.a-w.b;
}
bool maxb(p q,p w){return q.b-q.a<w.b-w.a;
}
vector<p>q,w;
int n,S,ans,sum1,sum2;
signed main()
{cin >> n >> S;for(int i=1;i<=n;i++){p d;cin >> d.s >> d.a >> d.b;ans+=d.s*max(d.a,d.b);//暂时都取大的 if( d.a>d.b )	q.pb(d),sum1+=d.s;else	w.pb(d),sum2+=d.s;}sum1%=S,sum2%=S;if( sum1+sum2<=S )//只能买一种 {sort(q.begin(),q.end(),maxa);sort(w.begin(),w.end(),maxb);int temp1=0,temp2=0;for(int i=0;i<q.size();i++){temp1+=min(sum1,q[i].s)*(q[i].a-q[i].b);sum1-=min(sum1,q[i].s);}for(int i=0;i<w.size();i++){temp2+=min(sum2,w[i].s)*(w[i].b-w[i].a);sum2-=min(sum2,w[i].s);}ans-=min(temp1,temp2);}cout << ans;
}