#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
string s;
int n;
map<char, long long>mp;
char a[N];
int cnt, cnt1;
long long sum;

int main() {
	freopen("song.in", "r", stdin);
	freopen("song.out", "w", stdout);
	cin >> s;
	cin >> n;
	char a1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] >= 97 && s[i] <= 122) {
			a1 = s[i];
			cnt1 = 0;
			continue;
		}
		if (s[i] == '1' || s[i] == '2' || s[i] == '3' || s[i] == '4' || s[i] == '5' || s[i] == '6' || s[i] == '7'
		        || s[i] == '8' || s[i] == '9' || s[i] == '0') {
			cnt1++;
			if (cnt1 >= 2) {
				sum -= mp[a1];
				mp[a1] = mp[a1] * 10 + (s[i] - '0');
				sum += mp[a1];
			} else {
				a[++cnt] = s[i - 1];
				sum += s[i] - '0';
				mp[a[cnt]] = s[i] - '0';
			}
		}
	}
	//cout << "字符个数:" << sum << endl;
	int c = n % sum;
	for (int i = 1; i <= cnt; i++) {
		if (mp[a[i]] < c) {
			c -= mp[a[i]];
		} else {
			cout << a[i];
			break;
		}
	}
	return 0;
}

D

如果已经分好了队，对于每一队来说，最后吃完的人吃完的时间是

$$\max_{i}\sum_{j=1}^{i}a_j+b_i$$

一定是按 $b$ 降序排序更优，证明如下：

设 $a$ 的前缀和为 $s$ ，假设最后排序方案存在 $(i,j)$ ，其中 $b_i<b_j,i<j$ ，那么

• $i$ 吃完的时间是 $s_{i-1}+a_i+b_i$
• $j$ 吃完的时间是 $s_{j-1}+a_j+b_j$

如果交换 $(i,j)$ ，则

• $i$ 吃完的时间是 $s_{j-1}+a_i+b_i$
• $j$ 吃完的时间是 $s_{i-1}+a_j+b_j$

容易发现前种情况两者取 max 不小于后种情况的两者取 max ，因此交换 $(i,j)$ 一定不劣。

因此，我们将人按照 $b$ 降序排序，设 $f_{i,j}$ 表示考虑前 $i$ 个人，第一队已经分配进去的人 $a$ 的和是 $j$ ，转移如下

$$f_{i,j}=\min(\max(j+b_i,f_{i-1,j}),\max(s_i-j+b_i,f_{i-1,j}))$$

可以去掉第一维，时间复杂度 $O(n^2V)$ 。

#include<bits/stdc++.h>
using namespace std;
int n,s,f[250005];
struct node{
	int a,b;
}t[505];
bool cmp(node x,node y){
	return x.b>y.b;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>t[i].a>>t[i].b;
	sort(t+1,t+n+1,cmp);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		s+=t[i].a;
		for(int j=s;j>=0;j--){
            f[j]=max(f[j],s-j+t[i].b);
			if(j>=t[i].a)f[j]=min(f[j],max(j+t[i].b,f[j-t[i].a]));
		}
	}
	int ans=1e9;
	for(int i=0;i<=s;i++)ans=min(ans,f[i]);
	cout<<ans;
}

// hd 表示朝向哪里走
// f 表示是否转弯
void dfs(int dep, int x, int y, int hd, bool f = 0) {
	if (dep == s.size()) {
		ans++;
		return ;
	}
	// 不转弯
	int nx = x + dx[hd], ny = y + dy[hd];
	if (nx > 0 && nx <= n && ny > 0 && ny <= m && a[nx][ny] == s[dep] )
		dfs(dep + 1, nx, ny, hd, f);
	// 转弯
	// 只有dep > 1 的时候才能转弯，否则会重复计数
	// 顺时针转弯
	nx = x + dx[(hd + 1) % 4], ny = y + dy[(hd + 1) % 4];
	if (nx > 0 && nx <= n && ny > 0 && ny <= m && dep > 1 && !f && a[nx][ny] == s[dep] )
		dfs(dep + 1, nx, ny, (hd + 1) % 4, 1);
	// 逆时针转弯
	nx = x + dx[(hd + 3) % 4], ny = y + dy[(hd + 3) % 4];
	if (nx > 0 && nx <= n && ny > 0 && ny <= m && dep > 1 && !f && a[nx][ny] == s[dep] )
		dfs(dep + 1, nx, ny, (hd + 3) % 4, 1);
}