C-Robot Collisions
题意：
在 (0～m) 的坐标轴上，机器人在碰到边界时会反向继续行走，已知(n)个机器人的初始位置和初始方向，每个机器人的速度为(1)，问每个机器人在哪个时刻爆炸，机器人爆炸当且仅当两个机器人在整数点相遇。
思路：
- 首先可以观察到只有机器人的初始位置的坐标的奇偶性相同时，才有可能发生碰撞，那么把问题分成两部分，奇坐标和偶坐标。
- 对于某一可能碰撞部分，先将机器人按初始坐标排序，我们分两方面考虑，一方面是不需要转向的，对于不需要转向的，只有一种可能，即左边的向右边行走，右边的向左边行走。对于这一部分，我们可以用栈来维护，即向右边走的入栈，遇到向左边走的出栈，这样就可以保证正确性。
- 另一方面，我们对于剩余的方向的(L)和方向为(R)的机器人，我们分别遍历，设(pos1<pos2)，对于(L)，我们按坐标从小到大遍历，对于相邻的两个机器人，其碰撞时刻一定是(pos1+(pos2-pos1)/2)，对于(R)，我们按坐标从大到小遍历，对于相邻的两个机器人，其碰撞时刻一定是(m-pos2+(pos2-pos1)/2)。
- 最后，方向(L)和方向(R)剩下的机器人最多都为(1)，当两个都为(1)是，可以通过两个机器人都碰到边界后进行碰撞.
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=300001;
const int INF=0x3f3f3f3f;
int n,m;
int a[MAXN];
int ans[MAXN];
map<int,int>mp;
char cc[MAXN];
struct node{
int pos,dir;
}s[MAXN];
bool cmp(node xx,node yy)
{
return xx.pos<yy.pos;
}
vector<node>v[2];
int main()
{
int T;
cin>>T;
while(T--){
v[0].clear();
v[1].clear();
mp.clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mp[a[i]]=i;
ans[i]=-1;
}
for(int i=1;i<=n;i++){
getchar();
scanf("%c",&cc[i]);
v[a[i]%2].push_back((node){a[i],cc[i]=='L'});
}
for(int i=0;i<=1;i++){
sort(v[i].begin(),v[i].end(),cmp);
int cnt=0;
for(int j=0;j<v[i].size();j++){
if(v[i][j].dir==0)s[++cnt]=v[i][j];
else{
if(cnt>0){
//cout<<i<<" "<<mp[s[cnt].pos]<<" "<<mp[v[i][j].pos]<<endl;
ans[mp[s[cnt].pos]]=(v[i][j].pos-s[cnt].pos)/2;
ans[mp[v[i][j].pos]]=(v[i][j].pos-s[cnt].pos)/2;
cnt--;
}
}
}
// for(int i=1;i<=n;i++){
// printf("%d ",ans[i]);
// }
// cout<<endl;
node lastl={0,0};
for(int j=0;j<v[i].size();j++){
if(v[i][j].dir==1&&ans[mp[v[i][j].pos]]==-1){
if(lastl.pos==0)lastl=v[i][j];
else{
//cout<<lastl.pos<<" "<<v[i][j].pos<<endl;
ans[mp[lastl.pos]]=lastl.pos+(v[i][j].pos-lastl.pos)/2;
ans[mp[v[i][j].pos]]=lastl.pos+(v[i][j].pos-lastl.pos)/2;
lastl=(node){0,0};
}
}
}
// for(int i=1;i<=n;i++){
// printf("%d ",ans[i]);
// }
// cout<<endl;
node lastr={0,0};
for(int j=v[i].size()-1;j>=0;j--){
if(v[i][j].dir==0&&ans[mp[v[i][j].pos]]==-1){
if(lastr.pos==0)lastr=v[i][j];
else{
//cout<<lastl.pos<<" "<<v[i][j].pos<<endl;
ans[mp[lastr.pos]]=m-lastr.pos+(lastr.pos-v[i][j].pos)/2;
ans[mp[v[i][j].pos]]=m-lastr.pos+(lastr.pos-v[i][j].pos)/2;
lastr=(node){0,0};
}
}
}
// for(int i=1;i<=n;i++){
// printf("%d ",ans[i]);
// }
// cout<<endl;
if(lastl.pos!=0&&lastr.pos!=0){
ans[mp[lastl.pos]]=((m-lastr.pos)+lastl.pos+m)/2;
ans[mp[lastr.pos]]=((m-lastr.pos)+lastl.pos+m)/2;
}
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
cout<<endl;
}
}
D-Armchairs
题意：
有(n)把椅子，至多有(n/2)个人坐在椅子上，问让所有有人坐的椅子都变空的最小代价是多少，坐在第(i)把椅子上的人移动到第(j)把椅子上的代价为 (abs(i-j))。
思路：
- 考虑(dp)，(dp[i][j])表示让前(i)把椅子的人移动到前(j)把空椅子上的人的最小代价。
- 把(dp)数组初始为(inf)，可以推出转移方程 (dp[i+1][j]=min(dp[i][j],dp[i][j-1]+abs(pos[i]-pos[j-1])))
代码：
#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
vector<int>a,b;
int dp[5005][5005]; //表示前i个移动到j个空位置的最小花费
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int num;
scanf("%d",&num);
if(num==0)a.push_back(i);
else b.push_back(i);
}
memset(dp,0x3f3f,sizeof dp);
dp[0][0]=0;
for(int i=0;i<a.size();i++){
dp[i+1][0]=0;
for(int j=1;j<=b.size();j++){
int x=b[j-1];
int y=a[i];
dp[i+1][j]=min(dp[i][j],dp[i][j-1]+abs(x-y));
}
}
cout<<dp[a.size()][b.size()]<<endl;
return 0;
}