题意与分析（CodeForces 580B）

\(n\)个人，告诉你\(n\)个人的工资，每个人还有一个权值。现在从这n个人中选出m个人，使得他们的权值之和最大，但是对于选中的人而言，其他被选中的人的工资不能超过他的工资+d。

这题用尺取法可以漂亮的解决。尺取法按照《挑战》一书的定义，是“指对数组保存一对下标(起点和终点)，然后根据实际情况交替推进两个端点直到得到答案”的一种方法，因为这种操作“很像是尺蠖（日文中称为尺取虫）爬行的方式”而得名。

具体到这题就是，都不用二分：按照工资排序后设定前后指针\(L,R\)，然后将\(R\)向前移动到最大的符合条件的区间，记录并更新长度，然后将\(L\)更新，再继续这样操作即可。复杂度为\(O(n)\)。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB emplace_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll=long long;

using repType=ll;

const int MAXN=100000+5;

int n,d;

vector<pair<ll,ll> > vec;

int main()

{

	QUICKIO

	cin>>n>>d;

	rep(i,1,n)

	{

		ll m,s; cin>>m>>s;

		vec.PB(MP(m,s));

	}

	sort(ALL(vec));

	int L=0,R=-1;

	ll ans=0, sum=0;

	while (L<n)

	{

		while(R+1<n && vec[R+1].fi-vec[L].fi<d)

			sum+=vec[++R].se;

		ans=max(ans,sum);

		sum-=vec[L++].se;

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

「日常训练」Kefa and Company（Codeforces Round #321 Div. 2 B）

题意与分析（CodeForces 580B）

代码

最新文章

热门文章