可以处理的最大任务

• 有一个tasks任务列表，需要处理其中的任务；
• tasks[i] = [si, ei]，该任务可以在si<=day<=ei之间的任意天处理；
• 一天仅可以完成一个任务，输出可以处理的最大任务数；
  输入描述：
  第一行输入任务数n;
  后n行表示每个任务的开始时间si和终止时间ei，1<=si<=ei<=100000;
  输出描述：
  可以处理的最大任务数

示例1
输入：
3
1 1
1 2
1 3
输出：
3

示例2
输入：
6
5 6
5 5
3 7
2 6
4 9
5 8
输出：
5

示例3
输入：
6
1 3
2 3
3 3
1 2
2 2
1 1
输出：
3
思路： 贪心算法，每个任务尽量在最后一天处理；

• 所有任务按照终止时间降序排序；
• i=0第一个任务可以直接处理；
• 从索引 i=1 开始遍历所有任务，若前一个任务的终止时间 > 当前任务的终止时间，则当前任务可以处理，因为前一个任务在最后一天处理，不影响当前任务在最后一天处理；
• 若前一个任务的终止时间=当前任务的终止时间，前一个任务处理后(最后一天已用)，endtime = pre_endtime - 1，即往前走一天，使用当前endtime判断能否处理当前i任务；
  • 若endtime >= si , 则可以处理；
  • 否则，不可以处理，则continue下一个任务；

# __author__ = "laufing"


class MaxTask:
    def solution(self, n, tasks):
        # 任务按照终止时间降序
        tasks.sort(key=lambda i:i[1], reverse=True)

        # 第一个任务是可以直接处理的
        result = 1
        endtime = tasks[0][1] # 表示前一个任务的终止时间
        # 从第二个任务开始遍历
        for i in range(1, n):
            # 前一个任务的终止时间 > 当前任务的终止时间
            if endtime > tasks[i][1]:
                result += 1
                endtime = tasks[i][1]
            else:
                # 前一个任务的终止时间 == 当前任务的终止时间
                if endtime-1 >= tasks[i][0]:
                    result += 1
                    endtime -= 1
                else:
                    continue
        print(result)


if __name__ == '__main__':
    max_task = MaxTask()
    while True:
        try:
            n = int(input().strip())
            tasks = []
            for i in range(n):
                tasks.append(list(map(int, input().strip().split())))
            max_task.solution(n, tasks)
        except KeyboardInterrupt:
            break

其他形式的解法：

 
n = int(input())
tasks = []
for i in range(n):
    tasks.append([int(x) for x in input().split(" ")])
 
tasks = sorted(tasks, key=lambda x: -x[1])
 
queue = []
end_time = 100000
result = 0
i=0
while(True):
    if(i>=n):
        while (len(queue) > 0) :
            temp = queue[0]
            queue.pop(0)
            if (end_time >= temp[0]) :
                result+=1
                end_time-=1
        break
    else :
        while (len(queue) > 0):
            if(tasks[i][1] < end_time) :
                temp = queue[0]
                queue.pop(0)
                if (end_time >= temp[0]) :
                    result+=1
                    end_time-=1 
                
            else :
                break
        queue.append(tasks[i])
        queue = sorted(queue, key=lambda x:x[0])
        end_time = tasks[i][1]
    
    i+=1
 
print(result)

 

员工派遣

 
 
nums = [int(x) for x in input().split(" ")]
x = nums[0]
y = nums[1]
count_x = nums[2]
count_y = nums[3]
left = 1
right = pow(10, 9)
while (True) :
    if(left >= right):
        break
    else :
        mid = (left + right) >> 1
        target = max(0, count_x - int(mid / y) + int(mid / (x * y))) + max(0, count_y - int(mid / x) + int(mid / (x * y)))
        if (mid - int(mid / x) - int(mid / y) + int(mid / (x * y)) >= target) :
            right = mid
        else :
            left = mid + 1
print(left)

 

快递员的烦恼

 
 
nums = [int(x) for x in input().split(" ")]
n = nums[0]
r = nums[1]
matrix = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
distiance_map = [0 for i in range(2000)]
for i in range(n):
    nums1 = [int(x) for x in input().split(" ")]
    distiance_map[nums1[0]] = i + 1
    matrix[0][i + 1] = nums1[1]
    matrix[i + 1][0] = nums1[1]
 
for i in range(r):
    nums1 = [int(x) for x in input().split(" ")]
    matrix[distiance_map[nums1[0]]][distiance_map[nums1[1]]] = nums1[2]
    matrix[distiance_map[nums1[1]]][distiance_map[nums1[0]]] = nums1[2]
 
#保存客户访问状态，因为有n个客户，所以最多有2的10次方个状态。
cache = [[float('inf') for i in range(n + 1)] for j in range(1024)]
 
#当前访问的客户状态以及距离
queue = []
queue.append([0, 0])
cache[0][0] = 0
while (True):
    if(len(queue)<=0):
        break
    else :
        position = queue.pop(0)
        print(position[0]);
        i=0
        while(True):
            if(i>n):
                break
            else :
                if(i==position[1] or matrix[position[1]][i] ==float('inf')):
                    i+=1
                    continue
                
                new_situation = position[0]
                if(i > 0):
                    new_situation =  position[0] | pow(2, i-1)
                
                
                if (cache[new_situation][i] > cache[position[0]][position[1]] + matrix[position[1]][i]) :
                    cache[new_situation][i] = cache[position[0]][position[1]] + matrix[position[1]][i]
                    queue.append([new_situation, i])
 
            i+=1
 
final_distiance = cache[pow(2, n) - 1][0]
if(final_distiance == float('inf')):
    print(-1)
else :
    print(final_distiance)

 

符号运算

nums = []
operations = []
 
#最大公约数
def gcd(a, b) :
    if(a % b == 0):
        return b 
    else:
        return gcd(b, a%b)
 
def eval_op ():
    global nums,operations
    nums1 = nums.pop()
    nums2 = nums.pop()
    x = operations.pop()
    result = [0,0]
    if(x == '*' or x == '+' or x == '-') :
        result[0] = nums2[0] * nums1[0]
    else :
        result[0] = nums2[0] * nums1[1]
    
 
    sum_a = nums2[1] * nums1[0]
    sum_b = nums1[1] * nums2[0]
    if(x == '*'):
        result[1] = nums2[1] * nums1[1]
    elif (x == '+'):
        result[1] = sum_a + sum_b
    elif (x == '-') :
        result[1] = sum_a - sum_b
    else :
        result[1] = nums2[1] * nums1[0]
    
    nums.append(result)
 
def get_priority(input_char):
    if(input_char == '+' or input_char == '-') :
        return 0
    else :
        return 1
        
    
 
input_str = input()
nums = []
operations = []
length = len(input_str)
current = ""
i = 0
while (i < length) :
    if (input_str[i].isdigit()) :
        while (True) :
            if(not input_str[i].isdigit()):
                break
            current += input_str[i]
            if (i + 1 >= length) :
                break
            i+=1
        nums.append([1, int(current)])
        current = ""
    elif (input_str[i] == '(') :
        operations.append(input_str[i])
    elif (input_str[i] == ')') :
        while (operations[0] != '(') :
            eval_op()
        operations.pop(0)
    elif(input_str[i] == ' '):
        i+=1
        continue
    else :
        while (len(operations)>0 and operations[0] != '('
            and get_priority(input_str[i]) <= get_priority(operations[0])) :
            eval_op()
        operations.append(input_str[i])
     
    i+=1
 
while (True) :
    if(len(nums) <= 1):
        break
    else :
        eval_op()
 
result = nums[0]
if (result[0] == 0) :
    print("ERROR")
else :
    up = gcd(result[0], result[1])
    result[0] /= up
    result[1] /= up
    output_str = ""
    if(result[0] * result[1] < 0):
        output_str += "-"
    if (abs(result[0]) == 1) :
        print(output_str+str(result[1]))
    else :
        print(output_str + str(abs(int(result[1]))) + "/" +str(abs(int(result[0]))))
    
   

 

伐木工

import functools
import sys
import copy
import re
import math
 
n =int(input())
cache = [0 for i in range(n+1)]
cache[0] = 0
memory = [[] for i in range(n+1) ]
 
for i in range(1,n+1):
    memory[i].append(i)
    cache[i] = i
 
i=1
while(True):
    if(i>n):
        break
    else :
        for j in range(1, i):
            if(cache[i] > cache[j] * cache[i - j]):
                continue
            elif(cache[i] < cache[j] * cache[i - j]):
                cache[i] = cache[j] * cache[i - j]
                memory[i] = []
                for k in range(len(memory[j])):
                    memory[i].append(memory[j][k])
                for k in range(len(memory[i-j])):
                    memory[i].append(memory[i-j][k])
            else :
                if(len(memory[i]) > len(memory[j]) + len(memory[i-j])):
                    memory[i] = []
                    for k in range(len(memory[j])):
                        memory[i].append(memory[j][k])
                    for k in range(len(memory[i-j])):
                        memory[i].append(memory[i-j][k])
    i+=1
 
result = memory[n]
result.sort()
output_str = ""
for j in range(len(result)):
    output_str += str(result[j]) + " "
print(output_str)
    

 

反射计数

import math
 
nums = [int(x) for x in input().split(" ")]
w = nums[0]
h = nums[1]
x = nums[2]
y = nums[3]
sx = nums[4]
sy = nums[5]
t = nums[6]
matrix = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    inupt_str = input()
    for j in range(w):
        matrix[i][j] = ord(inupt_str[j]) - ord('0')
    
 
 
result = 0
while (True):
    if(t<0):
        break
    else :
        if ((x + sx < 0) or (x + sx > w - 1)) :
            sx = -sx
        elif ((y + sy < 0) or (y + sy > h - 1)) :
            sy = -sy
        if (matrix[y][x] == 1) :
            result+=1
        
        x += sx
        y += sy
    
    t-=1
print(result)

 

分披萨

 
n =int(input())
nums = []
for i in range(n):
    nums.append(int(input()))
memory = [[0 for i in range(n)] for j in range(n)]
 
def backtrace(left, right) :
    global n,nums,memory
    if(nums[left] > nums[right]):
        left = (left + n + 1) % n
    elif(nums[left] < nums[right]):
        right = (right + n - 1) % n
    
 
    if (memory[left][right] <= 0) :
        if (left == right) :
            memory[left][right] = nums[left]
        else :
            new_left = (left + 1) % n
            new_right = (right + n - 1) % n
            memory[left][right] = nums[left] + backtrace(new_left, right)
            if(nums[right] + backtrace(left,new_right) > memory[left][right]):
                memory[left][right] = nums[right] + backtrace(left,new_right)
        return memory[left][right]
    else :
        return memory[left][right]
    
 
result = 0
i=0
while(True):
    if(i>=n):
        break
    else :
        left = (i + n + 1) % n
        right = (i + n - 1) % n
        target = backtrace(left, right)
        if(target+nums[i] > result):
            result = target+nums[i]
    i+=1
print(result) 

 

推荐多样性

 
n =int(input())
m = int(input())
input_matrix = []
while(True):
    try:
        input_matrix.append([int(x) for x in input().split(" ")])
    except:
        break
output_length = [0 for x in range(len(input_matrix))]
nums = []
while (True) :
    if(len(nums) >= n * m):
        break
    else :
        for i in range(len(input_matrix)):
            index = len(input_matrix[i])
            if(len(input_matrix[i]) > output_length[i] + 4):
                index = output_length[i] + 4
            j = output_length[i]
            while(j<index):
                nums.append(input_matrix[i][j])
                j+=1
            output_length[i] = index
output_str = ""
for j in range(n):
    for i in range(m):
        output_str += str(nums[i * n + j]) + " "
print(output_str[:-1]) 

 

贪心的歌手

 
params = [int(x) for x in input().split(" ")]
T = params[0]  
N = params[1]  
nums =  [int(x) for x in input().split(" ")]
matrix = []  
for i in range(N):
    matrix.append([int(x) for x in input().split(" ")])
 
 
for i in range(len(nums)):
    T-=nums[i]
 
moneys = []
i=0
while(True):
    if(i>=N):
        break
    else:
        temp1 = matrix[i][0]
        temp2 = matrix[i][1]
        j=0
        while(True):
            if(j>=T or temp1<=0):
                break
            else:
                moneys.append(temp1)
                temp1 = temp1- temp2
    i+=1
 
moneys = sorted(moneys, key=lambda x:-x)
 
result = 0
k = 0
while(True):
    if(k>=T):
        break
    else:
        result += moneys[k]
    k+=1
print(result)

 

螺旋数组矩阵(100)

 
directions = [0, 1, 0, -1, 0]
params = [int(x) for x in input().split(" ")]
k = params[0]  
n = params[1]  
 
matrix = [["*" for i in range(int((k - 1) / n + 1)) ] for j in range(n)]
start_x = 0
start_y = 0
count = 1 
index = 0 
 
while (True):
    if(count > k):
        break
    else :
        matrix[start_x][start_y] = str(count)
        count+=1
        new_x = start_x + directions[index]
        new_y = start_y + directions[index+1]
        
        if (new_x < 0 or new_x >= n or new_y < 0 or new_y >= (k - 1) / n +1 
            or matrix[new_x][new_y]!="*") :
            index = (index + 1) % 4
            start_x = start_x + directions[index]
            start_y = start_y + directions[index+1]
        else :
            start_x= new_x
            start_y= new_y
 
 
for i in range(n):
    output_str = ""
    for j in range(int((k - 1) / n + 1)):
        output_str += matrix[i][j]
        if (j != (k - 1) / n):
            output_str += " "
    print(output_str)