題目描述:

有一條彩色寶石項鏈，是由很多種不同的寶石組成的，包括紅寶石，藍寶石，鉆石，翡翠，珍珠等。有一天國王把項鏈賞賜給了一個學者，并跟他說，你可以帶走這條項鏈，但是王后很喜歡紅寶石，藍寶石，紫水晶，翡翠和鉆石這五種，我要你從項鏈中截取連續的一小段還給我，這一段中必須包含所有的這五種寶石，剩下的部分你可以帶走。如果無法找到則一個也無法帶走。請幫助學者找出如何切分項鏈才能夠拿到最多的寶石。

輸入描述:

我們用每種字符代表一種寶石，A表示紅寶石，B表示藍寶石，C代表紫水晶，D代表翡翠，E代表鉆石，F代表玉石，G代表玻璃等等，我們用一個全部為大寫字母的字符序列表示項鏈的寶石序列，注意項鏈是首尾相接的。每行代表一種情況。

輸出描述:

輸出學者能夠拿到的最多的寶石數量。每行一個

示例1:

輸入 ABCYDYE ATTMBQECPD 輸出 1 3

解題思路：

相當于構造一個動態的滑動窗口，窗口的大小依次遞增，最小為5，最大為輸入字符串的長度。然后用這個窗口依次從左向右框選字符，每框選依次，便進行依次判斷，如果符合題意，就輸出length-n，退出程序。

#include<iostream> #include<string.h> using namespace std;bool In(string str,int n){int i,j;int count=0;string s="ABCDE";for(i=0;i<5;i++){for(j=0;j<n;j++){if(s[i]==str[j]){count++;break;}}}if(count==5)return true;elsereturn false; }int main(){string str;string temp;int length;int n;int i;int k;cin>>str;length=str.length();for(n=5;n<=length;n++){for(i=0;i<length;i++){temp.clear();for(k=0;k<n;k++){temp.append(1,str[(i+k+1)%length]);}if(In(temp,n)){cout<<length-n<<endl;return 0;}}} }

歡迎留言交流。。。

總結

以上是生活随笔為你收集整理的NewCode----彩色宝石项链的全部內容，希望文章能夠幫你解決所遇到的問題。

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