dd爱科学1.0时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述大科学家d d dddd最近在研究转基因白菜白菜的基因序列由一串大写英文字母构成d d dddd经过严谨的推理证明发现只有当白菜的基因序列呈按位非递减形式时这株白菜的高附加值将达到最高于是优秀的d d dddd开始着手修改白菜的基因序列d d dddd每次修改基因序列的任意位需要的代价是1 11d 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种字符进一步降低复杂度。效率保障线性级别的高效算法轻松处理百万长度的字符串无超时风险。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,a;string s;ll zi[1000005];llcheck(ll x){ll l1,ra;while(lr){ll mid(lr)1;if(zi[mid]x)rmid;elselmid1;}returnl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;;cins;for(ll i0;in;i){ll xs[i];if(zi[a]x||a0)zi[a]x;elsezi[check(x)]x;}coutn-a;return0;}
