dd爱科学1.0【牛客tracker 每日一题】
dd爱科学1.0
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
大科学家d d dddd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，d d dddd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的d d dddd开始着手修改白菜的基因序列，d d dddd每次修改基因序列的任意位需要的代价是1 11，d d dddd想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价的是多少。
输入描述：
第一行一个正整数n ( 1 ≤ n ≤ 1000000 ) n(1≤n≤1000000)n(1≤n≤1000000)
第二行一个长度为n nn的字符串，表示所给白菜的基因序列
保证给出字符串中有且仅有大写英文字母
输出描述：
输出一行，表示最小代价
示例1
输入：
5 ACEBF输出：
1说明：
改成A C E E F ACEEFACEEF或者A C E F F ACEFFACEFF，都只用改动一个字符，所需代价最小为1 11
解题思路
本题核心是最长非递减子序列(LIS)贪心优化，最小修改代价等于字符串总长度减去最长非递减子序列的长度。题目要求将字符串修改为非递减序列，代价最小即保留最多的原字符，等价于求解最长非递减子序列。由于字符仅包含26种大写英文字母，结合贪心+二分查找算法，遍历字符串时维护非递减序列：当前字符大于等于序列末尾则直接追加，否则二分查找并替换序列中第一个大于它的元素。算法时间复杂度O ( n log 26 ) O(n\log26)O(nlog26)，极致高效，完美适配n ≤ 10 6 n \le 10^6n≤106的超大数据规模。
总结
核心逻辑：最小修改代价 = 总长度 - 最长非递减子序列长度，将问题转化为经典LIS求解。
关键操作：贪心维护序列、二分查找优化替换、仅26种字符进一步降低复杂度。
效率保障：线性级别的高效算法，轻松处理百万长度的字符串，无超时风险。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,a;string s;ll zi[1000005];llcheck(ll x){ll l=1,r=a;while(l<r){ll mid=(l+r)>>1;if(zi[mid]>x)r=mid;elsel=mid+1;}returnl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;;cin>>s;for(ll i=0;i<n;i++){ll x=s[i];if(zi[a]<=x||a==0)zi[++a]=x;elsezi[check(x)]=x;}cout<<n-a;return0;}