刚才的奶牛围栏问题，用python编程

nichloas

[code:1]
def findmaxFnum(list):
    """
    find a max number M to make the equation has no answer

    \sum a_i x_i = M
    a_i  belongs to 1,2,3,...
    x_i  belongs to 0,1,2,...
    a_i  given in list

    if finded, return M
    if not, return -1
   
    """
    list.sort()
    minnum = list[0]
    list = list[1:]

    newlist = list[:]

    ress = [0] * minnum
    process = 0

    while process < minnum-1:
        newlist.sort()
        curnum = newlist[0]
        residue = curnum % minnum
        if residue != 0 :
            if ress[residue] == 0:
                process += 1
                ress[residue] = curnum

        newlist[:1] = []
        for x in list:
            sum = curnum + x
            if sum not in newlist:
                newlist.append(sum)

    result = max(ress) - minnum
    if result <= 0:
        return -1
    else :
        return result

               

def processdata(list, maxcut):
    newlist = []
    for x in list:
        for i in range(maxcut + 1):
            tmp = x - i
            if tmp not in newlist :
                newlist.append(tmp)
    if 1 in newlist:
        return -1
    return findmaxFnum(newlist)

if __name__ == '__main__':
    ifile = file('fence.in')
    line = ifile.readline()
    words = line.split()
    datalen = int(words[0])
    maxcut = int(words[1])

    list = []

    for i in range(datalen):
        line = ifile.readline()
        list.append(int(line))

    ifile.close()

    result = processdata(list, maxcut)

    ofile = file('fence.out', 'w+')
    ofile.write('%i\n' % result)
    ofile.close()
[/code:1]

nichloas

如果要考虑速度，最内层数据结构应该采用minheap数据结构
但是为避免程序看起来太长，就省略了

hehe

nichloas

贴一个使用heap数据结构的版本，这个版本的heap.py并不完全，只提供了cow.py需要的函数

heap.py
[code:1]
import types

class heap:
    def __init__(self, data, fcmp=cmp):
        self.data = []
        self.fcmp = fcmp        
        if type(data) in [types.ListType, types.TupleType]:
            for x in data:
                self.append(x)
        else:
            self.append(data)


    def append(self, data):
        self.data.append(data)
        point = len(self.data)

        while point != 1:
            pson = point - 1
            pfather = point/2 - 1
            
            if self.fcmp(self.data[pson], self.data[pfather]) > 0:
                tmp = self.data[pson]
                self.data[pson] = self.data[pfather]
                self.data[pfather] = tmp
                point = point/2
            else :
                break

    def pop(self):
        rval = self.data[0]
        self.data[0] = self.data[-1]
        self.data.pop()

        point = 1
        
        while point <= len(self.data)/2:
            pfather = point - 1

            pson1 = point * 2 - 1
            pson2 = point * 2
            if pson2 >= len(self.data):
                pson = pson1
            elif self.fcmp(self.data[pson1], self.data[pson2]) > 0:
                pson = pson1
            else :
                pson = pson2

            if self.fcmp(self.data[pfather], self.data[pson]) < 0:
                tmp = self.data[pson]
                self.data[pson] = self.data[pfather]
                self.data[pfather] = tmp
                point = pson + 1
            else :
                break

        return rval

    def __iter__(self):
        return self.data.__iter__()
   
   

class maxheap(heap):
    def __init__(self,data):
        heap.__init__(self,data)



class minheap(heap):
    def __init__(self,data):
        fcmp = lambda x,y: cmp(y,x)
        heap.__init__(self,data,fcmp)
[/code:1]


cow.py

[code:1]
import heap


def findmaxFnum(list):
    """
    find a max number M to make the equation has no answer

    \sum a_i x_i = M
    a_i  belongs to 1,2,3,...
    x_i  belongs to 0,1,2,...
    a_i  given in list

    if finded, return M
    if not, return -1
   
    """
    list.sort()
    minnum = list[0]
    list = list[1:]

    myheap = heap.minheap(list)

    ress = [0] * minnum
    process = 0

    while process < minnum-1:
        curnum = myheap.pop()
        residue = curnum % minnum
        if residue != 0 :
            if ress[residue] == 0:
                process += 1
                ress[residue] = curnum

        for x in list:
            sum = curnum + x
            if sum not in myheap:
                myheap.append(sum)

    result = max(ress) - minnum
    if result <= 0:
        return -1
    else :
        return result

               

def processdata(list, maxcut):
    newlist = []
    for x in list:
        for i in range(maxcut + 1):
            tmp = x - i
            if tmp not in newlist :
                newlist.append(tmp)
    if 1 in newlist:
        return -1
    return findmaxFnum(newlist)

if __name__ == '__main__':
    ifile = file('fence.in')
    line = ifile.readline()
    words = line.split()
    datalen = int(words[0])
    maxcut = int(words[1])

    list = []

    for i in range(datalen):
        line = ifile.readline()
        list.append(int(line))

    ifile.close()

    result = processdata(list, maxcut)

    ofile = file('fence.out', 'w+')
    ofile.write('%i\n' % result)
    ofile.close()

[/code:1]

wsm

不太懂 不过想问一下 得到一个n后 如何确定>n的数都是可以被这组数组和成的呢 我这点没想出来

nichloas

我试着讲一下，不知道能不能讲清楚

假定有三个数分别为3,5,7
那么我们知道3n的数都可以被组合
那么剩下3n+1,3n+2的数

然后我们用5,7组合出最小的3n+1和3n+2的形式（分别为N,M）
然后得到的N-3, M-3就是不能被这几个数组合的，
从中挑一个最大的就是了






[quote:313adb7876="wsm"]不太懂 不过想问一下 得到一个n后 如何确定>n的数都是可以被这组数组和成的呢 我这点没想出来[/quote]