題意：
? ? ? 題意，哎！說道題意就蛋疼啊，比賽的時候就愣是把這個題目讀成數字可以隨意組合，比如123 可以拆成1 23 ，12 3 ，1 2 3，結果顯然，水題當神題，各種想不出來，然后就顯然的悲劇了，現在說下這個題目的意思給你一個串問你最少多少步操作可以把這個串變成合格的表達式組，每個合格表達式都是AB*的形式，A,B是數字，而且是1位的數字，只能是1位<哎！比賽的時候sb了>，然后AB*可以變成一個數字，也是1位的，是誰不重要，操作有兩種，一個是在任意位置上添加一個字母1-9或者是*,另一個就是可以任意交換兩個字符，問你變成合格的組合的最少步數，好像沒說明白題意啊，那么我在舉幾個例子。1*1：我們可以直接把中間的*和后面的1交換，變成11*，11*可以轉換成數字了，答案是1步11*234**：我們先把11*變成數字假如是A。34*變成B,那么就是A2B* 然后2B*可以轉換成一個數字了C，加上前面的A還是一個可發數字AC，所以是0步。*：要在前面加兩個數字變成AB*才能轉換成一個純數字串 所以是2

思路：

? ? ? 首先我們要知道，假如最終的*個數為x，最終的數字個數a肯定是 a >= x + 1,這樣的話我們的策略可以這樣，我們先看看數字個數夠不夠，如果不夠，那么先把數字填夠，<這里當然是填到等于x+1的個數了，能剩則剩>，還有就是要知道，根本不用填*因為填*就是在為自己增加負擔，填問數字我們就可以線性掃了，從前往后，對于每一個*如果前面的數字個數不滿足了，那么就把當前的*和最后面的一個數字交換就行了，這樣有點貪心的意思，具體看代碼吧。

#include<stdio.h>?
#include<string.h>
#include<queue>

int num[1100];
char str[1100];

int main ()
{
? ?int t ,i ,Ans;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%s" ,str);
? ? ? int l = strlen(str);
? ? ? int s1 = 0 ,s2 = 0;
? ? ? for(i = 0 ;i < l ;i ++)
? ? ? {
? ? ? ? ?if(str[i] == '*') num[i+1] = 1 ,s1 ++;
? ? ? ? ?else num[i+1] = 0 ,s2 ++;
? ? ? } ?
? ? ? int now = 0;
? ? ? if(s2 < s1 - 1) now = ?s1 + 1 - s2;
? ? ? Ans = now;
? ? ? for(i = 1 ;i <= l ;i ++)
? ? ? {
? ? ? ? ?if(num[i])?
? ? ? ? ?{
? ? ? ? ? ? if(now >= 2) now --;
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ?Ans ++;
? ? ? ? ? ? ? ?for(int j = l ;j > i ;j --)
? ? ? ? ? ? ? ?if(!num[j])
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? int t = num[i];
? ? ? ? ? ? ? ? ? num[i] = num[j];
? ? ? ? ? ? ? ? ? num[j] = t;
? ? ? ? ? ? ? ? ? now ++;
? ? ? ? ? ? ? ? ? break; ??
? ? ? ? ? ? ? ?}
? ? ? ? ? ? }
? ? ? ? ?}
? ? ? ? ?else now ++;
? ? ? }
? ? ? if(!num[l]) Ans ++;?
? ? ? if(!s1) Ans = 0;
? ? ? if(num[1] && l == 1) Ans = 2;?
? ? ? printf("%d\n" ,Ans);
? ?}
? ?return 0;
}

總結

以上是生活随笔為你收集整理的Known Notation 39届亚洲赛牡丹江站K题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。