还是菜,两题dp一题模拟
/*
反正就两个方向,往左或者往右,如果都不行,那就是-1
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x,y,d,t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&n,&x,&y,&d);
if(abs(y-x)%d==) {
printf("%d\n",abs(y-x)/d);
continue;
}
else {
if((y-)%d!= && (n-y)%d!=){
puts("-1");
continue;
}
int r=-,l=-;
if((n-y)%d==){
if((n-x)%d==) r=(n-x)/d;
else r=(n-x)/d+;
r+=(n-y)/d;
} if((y-)%d==){
if((x-)%d==) l=(x-)/d;
else l=(x-)/d+;
l+=(y-)/d;
} if(l==-) printf("%d\n",r);
else if(r==-) printf("%d\n",l);
else printf("%d\n",min(l,r));
}
} }
/*
给定一串字符,只有两个字母G,S,允许交换一次任意两个字母,问交换后最长连续的G是多长
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
int n,a[maxn];
int L[maxn],R[maxn],tot=;
int main(){ char s[maxn];
scanf("%d%s",&n,s+);
for(int i=;i<=n;i++){
if(s[i]=='G'){
tot++;
a[i]=a[i-]+;
}
else a[i]=a[i-];
}
for(int i=;i<=n;i++)
if(s[i]=='G') L[i]=L[i-]+;
else L[i]=;
for(int i=n;i>=;i--)
if(s[i]=='G') R[i]=R[i+]+;
else R[i]=; int ans=;
for(int i=;i<=n;i++){//要么是包括该点的左连续,要么是该点之前的左连续+该点之外的右连续+1
ans=max(ans,L[i]);
ans=max(ans,L[i-]+R[i+]+);
}
printf("%d\n",min(ans,tot));
}
/*
一次排序后,sum[i]表示每种专业选取i个人的最大值
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define ll long long
ll sum[maxn];
vector<int>a[maxn];
vector<ll>::iterator it;
int tot[maxn];
int cmp(int a,int b){
return a>b;
}//降序排列 int main(){
int n,m,id,val,mx=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d%d",&id,&val);
a[id].push_back(val);
tot[id]++;
}
for(int i=;i<=m;i++)
sort(a[i].begin(),a[i].end(),cmp); for(int i=;i<=m;i++){
ll tmp=;
for(int j=;j<a[i].size();j++){
tmp+=a[i][j];
if(tmp>)//总和为负的不能加
sum[j]+=tmp;
}
}
ll ans=;
for(int i=;i<n;i++)
ans=max(ans,sum[i]);
printf("%lld\n",ans); return ;
}