題目的意思就是說給定不超過四個詞的句子,將這幾個次進行全排列,然後在去下面給出的例子中進行匹配,如果某個全排列匹配成功的話,就求出其逆序數,找到符合情況的逆序數最小的情況,如果有多的選擇,則選擇編號最小的情況,並按照給定的格式進行輸出。
題目中說到就是子串中的單詞不會重復,但是匹配串會有單詞重復,如果說去每個匹配串中找到相應的單詞,並求出所有可能的逆序的話,這樣的任務量會很大。不如就是把子串所有的全排列全部匹配一遍,這樣的話會省去很多判斷的過程,對於編碼和時間都會有很大的改善。
那麼這道題的主要思路就是用到next_permutation()函數將子串進行全排列,然後把每種情況的逆序數求出來,然後和匹配串一一匹配,然後再重中找到最終的解。
#include#include #include #include using namespace std; struct node { char s[21][25]; int k; } v[10]; int main() { int n,m,k,f[4]; scanf("%d",&n); char a[4][20]; for(int i=0; i f[i]) sum++; if(sum>ans) continue; for(i=0; i =n) break; } if(i