贪心

要求切割数量尽可能多。当一个子串满足要求后，再将后面的字符加入该子串中，并不会使答案增多，并且会使后一个可能符合条件的子串变得不符合。所以，贪心策略就是，从左开始，能切割就切割。

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=2e6+10;
ll n,k;
char a[maxn],s[maxn];
ll num[maxn];
ll cnt[30];
int len,i,j;

int main(){
	scanf("%lld %lld",&n,&k);
    scanf("%s",a+1);
    
    len = strlen(a+1);
    // 将字符串转换成字母和数字的形式，s存字母，num存该字母出现次数 
	for(i=1,j=1;i<=len;){
    	if(a[i]>='a'&&a[i]<='z'){
    		s[j]=a[i];
    		i+=2;
    		if(i<=len){
    			ll tmp=0;
    			while(a[i]!=')'){
    				tmp=tmp*10+(a[i]-'0');
    				i++;
				}
				i++;
				num[j]=tmp;
				j++;
			}else{
				break;
			}
		}
	}
	ll diff=0,tmp=0,ans=0;
	for(i=1;i<j;){
		// 如果该字母没出现过 
		if(cnt[s[i]-'a']==0){
			diff++;
			cnt[s[i]-'a']++;
		}
		// 如果符合条件了 
		if((tmp+num[i])*diff>=k){
			// 计算符合条件需要的最少数量 
			ll sub = max(k/diff-tmp,1ll);
			while((tmp+sub)*diff<k){// 循环次数很少，不会超时 
				sub++;
			}
			num[i]-=sub;
			if(num[i]==0){// 如果最少数量也用光了当前字母，那么移动到下一个字母 
				i++;
			}
			// 否则，当前字母还有剩余，i不变，继续下一次统计 
			memset(cnt,0,sizeof cnt);
			diff=0;
			tmp=0;
			ans++;
		}else{
			tmp+=num[i];
			i++;
		}
	}
	if(ans==0){
		printf("-1");
	}else{
		printf("%lld",ans);
	}
    
    return 0;
}

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小美拿到了一个字符串，并希望将其切割成若干个连续子串，并使每个子串的权值不小于$k$，请你求出最多可以切割出的子串的数量。

字符串以连续段长度给出，如：a(2)b(2)c(2)表示$aabbcc$

字符串权值定义为，字符串长度乘以字符种类数，例如:"arcaea"权值为$6*4=24$

注意:a(2)a(2)也是合法数据

输入描述

第一行两个正整数$n,k(1\le k,n\le 10^{18})$，代表字符串长度和连续段最小权值。

第二行一个仅包含小写字母、数字和括号的字符串，长度不超过$10^6$

输出描述

如果无法切割，输出-1。否则输出最大数量。

样例

输入

7 6
a(2)b(2)a(3)

输出

2

说明

切割成aab和baaa。

输入

1000000000 5
x(1000000000)

输出

200000000