UVA - 1610 Party Games（聚会游戏）（构造）-白红宇

UVA - 1610 Party Games（聚会游戏）（构造）

阅读量：4705 次

发布时间：2019-06-10

本文共 1587 字，大约阅读时间需要 5 分钟。

题意：输入一个n(2<=n<=1000，n是偶数)个字符串的集合D，找一个长度最短的字符串S(不一定在D中出现)，使得D中恰好一半串小于等于S，另一半串大于S。如果有多解，输出字典序最小的解。

分析：找到最中间的两个串，直接按位构造。

#pragma comment(linker, "/STACK:102400000, 102400000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const double eps = 1e-8;const int MAXN = 1e3 + 10;const int MAXT = 10000 + 10;using namespace std;string s[MAXN];string solve(int n){ int mid = n / 2; int len = s[mid - 1].size(); string ans = ""; ans += 'A'; int i = 0; while(i < len){ while(ans[i] < 'Z' && ans < s[mid - 1]) ++ans[i];//只要i不是len-1且s[mid - 1][i]不是Z，得到的ans[i]都会比s[mid - 1]恰好大1,而如果i等于len-1，则得到的ans与s[mid-1]正好相等 if(ans >= s[mid - 1] && ans < s[mid]) return ans; if(s[mid - 1][i] != ans[i]) --ans[i];//如果s[mid - 1][i]不是Z，需要减1 ans += 'A'; ++i; }}int main(){ int n; while(scanf("%d", &n) == 1){ if(!n) return 0; for(int i = 0; i < n; ++i) cin >> s[i]; sort(s, s + n); printf("%s\n", solve(n).c_str()); } return 0;}