码蹄集 BD202401 补给

本文主要是介绍码蹄集 BD202401 补给，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

错误解法：简单将取半前后的综合排序后取最小值，这样没有考虑这样一种情况：取半的时机不对，也许取半某个大一点的P之后反而能进一步取一个补给点了呢？？对不对。这样简单排序只不过是“最省钱”的一种，而不是数量最多的一种。

#include<bits/stdc++.h>
using namespace std;
#define  MAX 1005
typedef struct Node
{
int p;
int flag;
}NNode;
NNode node[2005];bool cmp(const NNode &a,const NNode &b) { // &表示引用
return (a.p <= b.p);
}
int main( )
{int count = 0;
int ans = 0;
int N,B;
cin>>N>>B;
int a,b;
for(int i=0;i<N;i++)
{
cin>>a>>b;
node[count].p = a+b;
node[count++].flag = 0;
node[count].p = a/2+b;
node[count++].flag = 1;
}
sort(node,node+2N,cmp);
int flag = 0;
count = 0;
for(int i=0;i<2N;i++)
{
if(flag == 1 && node[i].flag == 1)
{
continue;
}
if(B<node[i].p) break;
ans++;
B-=node[i].p;
if(node[i].flag == 1) flag = 1;
}
cout<<ans;
return 0;
}

正确思路（贪心）：先按照不取半进行取，到无法容纳后一个时将先前最大值取半，进一步判断是否能容纳。贪心点在于使取半的收益最大：补给点数量能否加一

#include<bits/stdc++.h> 
using namespace std;
#define  MAX 1005
typedef struct Node
{int p;int s;int flag;
}NNode;
NNode node[2005];bool cmp(const NNode &a,const NNode &b) { // &表示引用return (a.p+a.s < b.p+b.s);
}
int main( )
{int count = 0;int ans = 0;int N;long long B;cin>>N>>B;int a,b;for(int i=0;i<N;i++){cin>>a>>b;node[count].p = a;node[count].s = b;node[count++].flag = 0;}sort(node,node+N,cmp);int flag = 0;int maxx = 0;for(int i=0;i<N;i++){if(B<node[i].p+node[i].s){if(flag == 0 && B+maxx/2 >= node[i].p+node[i].s) {flag = 1;ans++;B+=maxx/2;B=B - node[i].s - node[i].p;continue;}break;}B=B - node[i].s - node[i].p;maxx = max(maxx,node[i].p);ans++;}cout<<ans;return 0;
}