Skip to content

Instantly share code, notes, and snippets.

@yanring
Created April 2, 2019 11:40
Show Gist options
  • Save yanring/d7508979df9d6f9afe340927fe871ce8 to your computer and use it in GitHub Desktop.
Save yanring/d7508979df9d6f9afe340927fe871ce8 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
// input
int n,w,tmp,res=0,flag;
cin >> n;
cin >> w;
vector<int> weight(n,0);
flag = n;
// vector<bool> flag(n,0);
for(int i = 0; i < n ; i++){
cin >> tmp;
weight[i] = tmp;
}
// sort
sort(weight.begin(), weight.end());
// combine
// 排序后,首尾指针往中间逼近
int l=0,r=weight.size()-1;
while(l<r){
if(weight[l]+weight[r] <= w){
l++;
}else{
res+=2;
flag-=2;
l++;
r--;
}
}
res += (int) ceil(flag/2.0);
cout <<res <<endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment