双指针Level3
都是练习题了，题单在这里：https://codeforces.com/edu/course/2/lesson/9/3/practice。
A
思路
可能会发生多次循环，先判断一下有没有可能发生循环，如果有先计算。
我们再将数组扩展到两倍，然后进行双指针操作。注意下标的处理（可能超过\(n-1\)）和数组越界的情况。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll p; cin>>p;
std::vector<ll> a;
ll tot=0;
for(int i=0;i<n;i++)
{
ll t; cin>>t;
a.push_back(t);
tot+=t;
}
for(int i=0;i<n;i++)
{
a.push_back(a[i]);
}
ll ans=0;
if(tot<p)
{
ans+=(p/tot)*n;
p-=(p/tot)*tot;
}
ll l=0,r;
ll sum=0;
ll st=0;
ll cnt=1e9;
for(r=0;r<2*n;r++)
{
sum+=a[r];
while(sum-a[l]>=p && l+1<2*n)
{
sum-=a[l];
l++;
}
if(sum>=p)
{
if(cnt>r-l+1)
{
cnt=r-l+1;
st=(l+1)%n;
}
}
}
cout<<(st==0?n:st)<<" "<<ans+cnt<<" "<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
B
思路
跟之前的题目一样，只不过这里是求长度和。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for (int i = 0; i < n; ++i)
{
cin>>a[i];
}
int l=0,r;
ll sum=0;
ll ans=0;
for(r=0;r<n;r++)
{
sum+=a[r];
while(sum>s)
{
sum-=a[l];
l++;
}
ans+=1ll*(r-l+2)*(r-l+1)/2;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
C
思路
要求的是有都多少对的差是大于\(s\)的，我们只需要找到第一个不符合的情况，在此前面都是符合当前情况。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
int l=0,r;
ll ans=0;
for(r=0;r<n;r++)
{
while(a[r]-a[l]>s)
{
l++;
}
ans+=l;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
D
思路
不妨将全部服装都混合在一起，从小到大进行排序，这样通过左右指针维护一个区间，可以不断取\(min\)，保证是最小的情况。
在进行指针操作时，我们需要维护的是一个拥有一套服装的区间，如果这个不满足，我们继续加，否则，我们开始对这个区间进行操作。
我们可以通过一个桶来记录当前的服装数目（这里指特定的：鞋子 衬衫
裤子等等）。当满足条件时，我们对左指针进行操作，直到特定的服装少于一件为止，并更新答案，记录对应的区间起点和终点。
这样我们就可以确定选择的服装是在哪一个特定的区间，然后对没有选择的服装进行选择即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
std::vector<pair<int,int>> v;
for(int i=0;i<4;i++)
{
int n; cin>>n;
for(int j=0;j<n;j++)
{
int x; cin>>x;
v.push_back({x,i});
}
}
sort(v.begin(),v.end());
int l=0,r=0;
int num=0;
std::vector<int> flag(v.size(),0);
int ans=1e9;
int st=0,ed=0;
std::vector<int> a(4);
for(r;r<v.size();r++)
{
if(flag[v[r].second]==0)
{
num++;
}
flag[v[r].second]++;
if(num<4) continue;
while(flag[v[l].second]>1)
{
flag[v[l].second]--;
l++;
}
if(ans>v[r].first-v[l].first)
{
ans=v[r].first-v[l].first;
st=l,ed=r;
}
}
for(int i=st;i<=ed;i++)
{
if(!a[v[i].second])
{
a[v[i].second]=v[i].first;
}
}
for(int i=0;i<4;i++) cout<<a[i]<<" ";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
E
思路
这里多了一个\(weight\)，正常处理就行。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> w(n,0),c(n,0);
for(int i=0;i<n;i++) cin>>w[i];
for(int i=0;i<n;i++) cin>>c[i];
int l=0,r=0;
ll sum=0;
ll cost=0;
ll ans=0;
for(r;r<n;r++)
{
sum+=w[r];
cost+=c[r];
while(sum>s)
{
sum-=w[l];
cost-=c[l];
l++;
}
ans=max(cost,ans);
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
F
思路
比较麻烦的一点是：可能\(t\)中不存在而\(s\)中存在。所以一旦遇到这种情况，我们一直右移动左指针，直到这种情况不存在为止，这时
也会越过那个非法的字母。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n,m; cin>>n>>m;
string s,t; cin>>s>>t;
std::map<int, int> map;
for(int i=0;i<m;i++)
{
map[t[i]-'a']++;
}
std::map<int, int> mp;
int l=0,r=0;
ll ans=0;
for(r;r<n;r++)
{
mp[s[r]-'a']++;
if(mp[s[r]-'a']>map[s[r]-'a'])
{
while(s[l]!=s[r])
{
mp[s[l]-'a']--;
l++;
}
mp[s[l]-'a']--;
l++;
}
ans+=r-l+1;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
G
暂时没写
H
思路
不能想到，我们先选择比较大的数字，这样更快让其最大。
先对\(a、b\)排序，不妨先全部选择\(a\)，后面再用双指针进行处理：
我们用一个右指针指向所选择的\(a\)的末端，一个左指针指向\(b\)的开端，然后进行左指针右移，不断添加，如果不符合题意，则将右指针左移动，更新答案。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
ll n,m; cin>>n>>m;
ll s,A,B; cin>>s>>A>>B;
std::vector<ll> a(n,0),b(m,0);
for(auto &t: a) cin>>t;
for(auto &t: b) cin>>t;
sort(a.begin(),a.end(),greater<ll>());
sort(b.begin(),b.end(),greater<ll>());
ll r=min(n,s/A)-1;
ll sum=(r+1)*A;
ll ans=0;
for(int i=0;i<=r;i++) ans+=a[i];
ll l=0;
ll cur=ans;
for(l;l<min(s/B,m);l++)
{
sum+=B;
cur+=b[l];
while(sum>s)
{
sum-=A;
cur-=a[r];
r--;
}
ans=max(ans,cur);
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
I
暂时没写
