Milica and String
题目大意:我们给定一个长为n的字符串s,s仅由’A’和’B’两种字符组成,我们要使s中恰好有k个’B’,我们可以进行的操作是:选择一个整数i,和一个字符c,每次操作将s的前i个字符全部改成c。
思路:我们从后往前访问,记录每个位置后面’B’的个数,如果a[1]==n,那么就说明不用进行操作,如果a[1][HTML_REMOVED]m,那么就要将一些B改成A,也是从头遍历,不过需要累计B的个数。然后适时输出。
#include<bits/stdc++.h>
using namespace std;
int a[200];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
string s;
cin>>s;
int c=0;
for(int i=0;i<=n;i++) a[i]=0;
for(int i=s.size()-1;i>=0;i--)
{
if(s[i]=='B') a[i]=a[i+1]+1;
else a[i]=a[i+1];
}
if(a[0]<m)//shao
{
printf("1\n");
for(int i=0;i<n;i++)
{
if(s[i]=='A')
{
a[0]++;
if(a[0]==m)
{
printf("%d B\n",i+1);
break;
}
}
}
}
else if(a[0]==m) printf("0\n");
else
{
printf("1\n");
for(int i=0;i<n;i++)
{
if(s[i]=='B')
{
a[0]--;
if(a[0]==m)
{
printf("%d A\n",i+1);
break;
}
}
}
}
}
}
Milena and Admirer
题目大意:给定一个数组a[],我们想使数组变成非递减数组,我们可以进行的操作是:
每次选择一个i和x,然后用x和ai-x来代替ai.
问想要实现的话,最少操作多少次。
思路:我们如果从前往后改,前后容易顾不着,所以我们最好从后往前来操作,最后一个字符不进行操作用c记录这个数字,然后对于每一个访问到的数字,判断与c的关系,如果小于等于就 无所谓,如果大于就要来考虑进行操作。现在最关键的就是操作策略,这也是出错的地方,原始思路想着要让后面尽可能的大,于是想着每次切c(对半切不合要求的时候),但是这样固然是能切到的最大的,但是c会被更新成c或者a[i]%c,a[i]%c可能很小,这就不如均分来得好。所以切割策略应该是尽可能地等分,至于分地份数,就要保证最大地小于等于c,那么就是k=a[i]/c上取整份,然后新的c是小的那就是a[i]/k下取整。那么就实现了最优切割。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
int c=a[n];
int ans=0;
for(int i=n-1;i>=1;i--)
{
if(a[i]>c)
{
//切a[i]/c+1段
//余a[i]/c
int k=ceil(a[i]*1.0/c);
ans += k-1;
c=floor(a[i]*1.0/k);
}
else c=a[i];
//printf("%lld %lld\n",ans,c);
}
printf("%lld\n",ans);
}
}