CFR-679C Perform Easily 题解

题目大意

给你六根弦，每个弦有自己的权值，你需要用这六根弦弹出n个音调，可以任意用六根弦的任意一个位置弹奏音调，弹出的音调为这根弦的权值加上你选的位置，即a[i]+pos，问最小的位置极差为多少。

解题思路

这场比赛太毒了，c题1900。。

感觉这题想到了就不难，他的难点在于最小值和最大值都是固定的。

可以先定住最小值或者最大值，然后使端点值缩减即可。

用一个pair型的set，first为位置，second为所选的弦，刚好set会自动排序，按照pair的first来从小到大排序。

利用这个性质，就可以很好的枚举出最小值，只需要更改端点值即可。

（这个思路真的很妙。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << "#x" << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

const int N = 1e5 + 5;
set<pll> s;
int a[10], b[N], id[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	rep(i, 1, 6) cin >> a[i];
	sort(a + 1, a + 7);
	int n; cin >> n;
	rep(i, 1, n)	cin >> b[i], id[i] = 1;
	sort(b + 1, b + 1 + n);
	rep(i, 1, n)	s.insert({ b[i] - a[1],i });//定住最大值
	ll ans = 1e18;
	while (1) {
		auto p = --s.end();
		ll t = p->se;
		s.erase(p);
		if (id[t] == 6)	break;
		id[t]++;//使最大的最小值减小
		s.insert({ b[t] - a[id[t]],t });
		ans = min(ans, s.rbg()->fi - s.bg()->fi);
	}
	cout << ans << endl;
	return 0;
}