贪心+two-pointer
考虑贪心,首先升序排序,每次选择能与当前最大的配对的最大数
比如w=10,序列为1,2,3,4,5,6,7
第一次能与7配对的最大的是3,∵7+3>=10,且3最大
#include <bits/stdc++.h>
#define N 30010
using namespace std;
int w, n;
int a[N];
bool st[N];
int main()
{
cin >> w >> n;
for(int i = 0; i < n; ++ i) cin >> a[i];
sort(a, a + n);
int res = 0;
for(int i = 0, j = n - 1; i < n; ++ i)
{
if(st[i] == 1) continue;
while(i < j && (st[j] || (a[i] + a[j] > w))) j -- ;
st[i] = st[j] = 1;
res ++ ;
}
cout << res << endl;
}
对不起,发错地方了
你的Latex渲染失败啦
??什么意思