链接：http://codeforces.com/contest/1082
A. Vasya and Book
题意：
n,x,y,d
一本电子书有n页，每一次翻动只能往前或者往后翻d页。求x->y页最少需要多少步。只能在（1~n)之间翻。具体细节看题目吧。博客仅作记录
int t,n,x,y,d;
int calc(int x,int y)
{
return abs(x-y)/d;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&x,&y,&d);
int res = abs(x-y);
if(res%d==0)
{
cout<<res/d<<endl;continue;
}
int ans = inf;
if((y-1)%d==0)
{
ans = min(ans,(int)ceil((x-1.)/d)+(y-1)/d);
}
if((n-y)%d==0)
{
ans = min(ans,(int)ceil((double)(n-x)/d)+(n-y)/d);
}
if(ans == inf)
ans = -1;
cout<<ans<<endl;
}
return 0;
}
B. Vova and Trophies
渣渣的代码：
char s[200010];
int d[200010];
int n;
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
int num = 0;
for(int i=1;i<=n;i++)
if(s[i]=='G')
num++;
int ans = 0;
for(int i=1;i<=n;i++)
{
if(s[i]!='G')
{
d[i] = 0;
}
else
{
d[i] = 1;
if(s[i-1] == 'G')
d[i] = d[i-1]+1;
}
}
for(int i=1;i<=n;i++)
{
ans = max(ans,d[i]);
if(s[i-d[i]]=='S'&&d[i]<num)
{
if(s[i-d[i]-1]=='G')
{
if(d[i]+d[i-d[i]-1]<num)
ans = max(ans,d[i]+1+d[i-d[i]-1]);
else
ans = max(ans,d[i]+d[i-d[i]-1]);
}
ans = max(ans,d[i]+1);
}
}
printf("%d\n",ans);
return 0;
}
大神的代码
#include <bits/stdc++.h>
using namespace std;
int res,pre,cnt,g;
int main()
{
int n;
cin>>n;
while(n--)
{
char s;
cin>>s;
if(s=='G')cnt++,g++;
else pre = cnt,cnt = 0;
res = max(res,cnt+pre+1);
}
cout<<min(g,res);
return 0;
}
C. Multi-Subject Competition
vector<int> s[100010];
int n,m;
bool cmp(int a,int b)
{
return a>b;
}
bool cmp2(vector<int>a,vector<int> b)
{
return a.size()>b.size();
}
int main()
{
cin>>n>>m;
int t,r;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&t,&r);
s[t].push_back(r);
}
int mi = 0;
for(int i=1;i<=m;i++)
{
sort(s[i].begin(),s[i].end(),cmp);
for(int j=1;j<s[i].size();j++)
s[i][j] += s[i][j-1];
mi = max(mi,(int)s[i].size());
}
sort(s+1,s+m+1,cmp2);
int ans = 0;
for(int i=0;i<mi;i++)
{
int sum = 0;
for(int j=1;j<=m;j++)
{
if(i>=s[j].size())break;
sum = max(sum,sum+s[j][i]);
//printf("%d %d\n",j,s[j][i]);
}
//cout<<sum<<endl;
ans = max(ans,sum);
}
cout<<ans<<endl;
return 0;
}
大神的代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,s,r,k,c,mx,a[200000],l;
pair<long long,long long> p[200000];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>s>>r;
p[i]={s,-r};
}
sort(p,p+n);
for(int i=0;i<n;i++)
{
if(p[i].first!=l)
{
k=0; c=0; l=p[i].first;
}
c-=p[i].second;
k++;
if(c>0)
a[k]+=c;
mx=max(mx,a[k]);
}
cout<<mx;
return 0;
}