codeforces 202B Brand New Easy Problem

      题目的意思就是说给定不超过四个词的句子，将这几个次进行全排列，然后在去下面给出的例子中进行匹配，如果某个全排列匹配成功的话，就求出其逆序数，找到符合情况的逆序数最小的情况，如果有多的选择，则选择编号最小的情况，并按照给定的格式进行输出。

     题目中说到就是子串中的单词不会重复，但是匹配串会有单词重复，如果说去每个匹配串中找到相应的单词，并求出所有可能的逆序的话，这样的任务量会很大。不如就是把子串所有的全排列全部匹配一遍，这样的话会省去很多判断的过程，对于编码和时间都会有很大的改善。

     那么这道题的主要思路就是用到next_permutation()函数将子串进行全排列，然后把每种情况的逆序数求出来，然后和匹配串一一匹配，然后再重中找到最终的解。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<n; i++)
        scanf("%s",a[i]);
    scanf("%d",&m);
    for(int i=0; i<n; i++)
        f[i]=i;
    for(int i=0; i<m; i++)
    {
        scanf("%d",&v[i].k);
        for(int j=0; j<v[i].k; j++)
            scanf("%s",v[i].s[j]);
    }
    int p=20,ans=10000;
    do
    {
        int sum=0,i;
        for(i=0; i<n; i++)
            for(int j=0; j<i; j++)
                if(f[j]>f[i]) sum++;
        if(sum>ans) continue;
        for(i=0; i<m; i++)
        {
            int k=0,j;
            for(j=0; j<v[i].k&&k<n; j++)
                if(strcmp(a[f[k]],v[i].s[j])==0) k++;
            if(k>=n) break;
        }
        if(i<m&&(sum<ans||sum==ans&&p>i)) p=i,ans=sum;
    }
    while(next_permutation(f,f+n));
    if(p==20) printf("Brand new problem!\n");
    else
    {
        printf("%d\n[:",p+1);
        int t=n*(n-1)/2+1-ans;
        for(int i=0; i<t; i++) printf("|");
        printf(":]\n");
    }
    return 0;
}

codeforces 202B Brand New Easy Problem,布布扣,bubuko.com

codeforces 202B Brand New Easy Problem

原文：http://blog.csdn.net/knight_kaka/article/details/21743415