题意:
思路:
要么先选low值大的,要么先选high值大的,分两种情况讨论。
每次只要选了的low值和>=x或者c-未选的high值和>=x就肯定满足了。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn = 50+5; 8 9 int n,c,x,lowtot,hightot;10 11 struct node12 {13 int low,high;14 bool operator< (const node& rhs) const15 {16 return low > rhs.low;17 }18 }a[maxn];19 20 bool cmp(node a, node b)21 {22 return a.high>b.high;23 }24 25 int main()26 {27 //freopen("in.txt","r",stdin);28 int T;29 scanf("%d",&T);30 while(T--)31 {32 lowtot = hightot = 0;33 scanf("%d%d%d",&n,&c,&x);34 for(int i=1;i<=n;i++)35 {36 scanf("%d%d",&a[i].low,&a[i].high);37 lowtot += a[i].low;38 hightot += a[i].high;39 }40 int sum = 0;41 int ans = 0;42 sort(a+1,a+n+1);43 int tmp = hightot;44 for(int i=1;i<=n;i++)45 {46 sum += a[i].low;47 ans++;48 hightot -= a[i].high;49 if(sum>=x || c-hightot>=x) break;50 }51 52 sum = 0;53 int ans2 = 0;54 sort(a+1,a+n+1,cmp);55 hightot = tmp;56 for(int i=1;i<=n;i++)57 {58 sum += a[i].low;59 ans2++;60 hightot -= a[i].high;61 if(sum>=x || c-hightot>=x) break;62 }63 printf("%d\n",min(ans,ans2));64 }65 return 0;66 }