摘要
Title: 1443. 拍照
Tag: 模拟
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1443. 拍照

• 题意

  农夫约翰在给他编号为 1…N 的 N 头奶牛排队拍照。
  约翰一开始计划从左向右数第 i 个位置排编号为 ai 的奶牛，他在一张纸上写下了排列 a1,a2,…,aN。
  不幸的是，这张纸刚刚被小偷偷走了！
  幸好约翰仍然有机会恢复他之前写下的排列。
  在这张纸被偷走之前，奶牛贝茜记录了序列 b1,b2,…,bN−1，对于每一个 1≤i<N 满足 bi=ai+ai+1。
  基于贝茜的信息，帮助约翰恢复可以产生序列 b 的“字典序最小”的排列 a。
  排列 x 字典序小于排列 y：如果对于某个 j，对于所有 i<j 均有 xi=yi，且有 xj<yj（换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y）。
  保证存在至少一个满足条件的 a。

• 思路

  只要a[0]确定，那么后头的都确定了，枚举a[0]即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-15 13:47:36
  FilePath: \ACM\Acwing\1443.py
  LastEditTime: 2022-02-15 14:02:49
  '''
  from collections import Counter
  
  b = []
  
  if __name__ == "__main__":
      n = int(input())
      a = list(map(int, input().split()))
      for i in range(1, a[0]):
          d = Counter()  #记录是否重复
          tmp = []  #被记录的字典序
  
          tmp.append(i)
          d[i] += 1
          t = i  #记录原数组的数
          flag = 0  #判断是否重复
          for j in range(n - 1):
              if d[a[j] - t] or a[j] - t <= 0:
                  flag = 1
                  break
              d[a[j] - t] = 1
              tmp.append(a[j] - t)
              t = a[j] - t
          if flag == 0:
              b.append(tmp)
      b.sort()
      for i in b[0]:
          print(i, end=" ")