C. Perform Easily
给出6根弦,每根对应一个$a_i$
现在有一个乐谱 每个音符用$b_i$ 表示
例如样例：
1
2
3
| 琴弦的值ai：1 1 2 2 3 3
有几个音符：7
每个音符的值bi：13 4 11 12 11 13 12
|
每个音符在不同琴弦的对应位置不同
例如$b_i=13$ 在$a_i=3$的琴弦上 所在位置为$b_i-a_i=10$
定义一个乐谱的难度等于 相距最大的两个音符的位置差
每个音符要在哪根琴弦上弹奏由你来定使得这个乐谱最小的难度
利用set模拟
假设最初所有音符都在最后一根琴弦上(ai已经升序排列)
将所有音符以pair(${b_i-a_6,i}$)存入set
于是模拟贪心的过程
每次将最右端即$(b_i-a_x)$ 最小的音符移动到上一根琴弦变为$(b_i-a_{x-1})$
注意$a_x$已经是升序排列 移动到上一根琴弦的音符一定会往左移动
反复操作每次将位置最右的音符往左靠 能使得所有音符相邻间距尽量小
只要每次计算出最左端音符和最右端音符的距离差更新答案即可
这个模拟过程实际上是固定了$(b_i-a_x)$的最大值 贪心移动最小值
“定一值动一值”这种处理方法比较常见且实用 在许多题目中也有类似应用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=1e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;
set<P>st;
ll a[10],b[Max];
int id[Max];
int main(){
Turnoff;
for(int i=0;i<6;i++)cin>>a[i];
sort(a,a+6);
int n;cin>>n;
for(int i=1;i<=n;i++){
id[i]=5;cin>>b[i];
st.insert({b[i]-a[id[i]],i});
}
ll ans=(*st.rbegin()).first-(*st.begin()).first;
while(true){
auto p=st.begin();
int u=(*p).second;
st.erase(p);
if(!id[u])break;
id[u]--;
st.insert({b[u]-a[id[u]],u});
ans=min(ans,(*st.rbegin()).first-(*st.begin()).first);
}
cout<<ans<<endl;
}
|