安排机器

import sys

class node():
    def __init__(self,time,level):
        self.time = time
        self.level = level
#读取第一行获取机器数量和任务数量
line = list(map(int,list(sys.stdin.readline().strip().split(' '))))
machineNum = line[0]
jobNum = line[1]
machines = []
jobs = []
#读取每台机器的最大工作时间和机器等级
for i in range(machineNum):
    machineInfo = list(map(int,list(sys.stdin.readline().strip().split(' '))))
    time = machineInfo[0]
    level = machineInfo[1]
    machine = node(time,level)
    machines.append(machine)
#读取每个任务需要的完成时间和任务的难度系数
for j in range(jobNum):
    jobInfo = list(map(int,list(sys.stdin.readline().strip().split(' '))))
    time = jobInfo[0]
    level = jobInfo[1]
    job = node(time,level)
    jobs.append(job)
#根据时间排序
machines.sort(key = lambda x:(x.time,x.level),reverse = True)
jobs.sort(key = lambda x:(x.time,x.level),reverse = True)
#收益
profit = 0
count = 0
level = [0]*105
#对job根据时间排序，先完成时间大的收益更多；对符合条件的机器选择最接近的level
j = 0
for i in range(jobNum):#循环选取时间最大的job
    #在时间条件（机器时间>任务时间）满足的情况下
    while j< machineNum and machines[j].time>=jobs[i].time:
        level[machines[j].level] += 1
        j += 1
    for k in range(jobs[i].level,101):
        if level[k]:
            count += 1
            level[k] -= 1
            profit += 200 * jobs[i].time + 3 * jobs[i].level
            break
print(count,end=' ')
print(profit)

//安排机器
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn  = 1e5 + 10;
struct node{  int time,grade;
}machine[maxn],task[maxn]; 

int cnt[105];

int cmp(node a,node b){  if(a.time==b.time){  return a.grade>b.grade;  }  return a.time>b.time;
}

int main(){  int numMachine,numTask;  scanf("%d%d",&numMachine,&numTask);  for(int i=0;i<numMachine;i++){  scanf("%d%d",&machine[i].time,&machine[i].grade);  }  for(int i=0;i<numTask;i++){  scanf("%d%d",&task[i].time,&task[i].grade);  }  sort(machine,machine+numMachine,cmp);  sort(task,task+numTask,cmp);
// for(int i=0;i<numMachine;i++){
// printf("%d %d\n",e[i].time,e[i].grade);
// }
// for(int i=0;i<numTask;i++){
// printf("%d %d\n",f[i].time,f[i].grade);
// }    int num = 0;  LL ans = 0;  memset(cnt,0,sizeof(cnt));  int i,j,k;  for(i=0,j=0;i<numTask;i++){ //对于每个任务而言  while(j<numMachine && machine[j].time>=task[i].time){  cnt[machine[j].grade]++;  j++;  }  for(k=task[i].grade;k<=100;k++){  if(cnt[k]){  num++;  cnt[k]--;  ans = ans+200*task[i].time + 3*task[i].grade;  break;  }  }  }  printf("%d %lld\n",num,ans);  return 0;
}

nums = list(map(int,input().split()))
machine = []
duty = []
for i in range(nums[0]):
    # nums[0]个机器
    machine.append(list(map(int,input().split())))
    (2790)# [zi, wi]
for j in range(nums[1]):
    duty.append(list(map(int,input().split())))
    # [xi, yi]
(2791)# 根据时间排序，若时间一致，则根据等级排序
machine = sorted(machine,key = lambda x:(x[0],x[1]),reverse = True)
duty = sorted(duty,key = lambda x:(x[0],x[1]),reverse = True)
# profile = 200*xi+3*yi，说明时间大的收益更多
profile = 0 (2792)#总利润
count = 0 # 计数
j = 0 (2793)# 表示选择第j个机器,选择的机器需要和任务的等级最接近，效率才能最大

# hash_dict = {}
(2794)# #用来存储机器等级的数量，{1:1}表示等级为1的机器有1个
(2795)# for k in range(len(machine)):
#     if machine[1] in  hash_dict:
(2796)#         hash_dict[machine[1]]+= 1
#     else : hash_dict[machine[1]] = 1
(2797)# # 统计后根据等级排序
(2798)# level=sorted(hash_dict.items(),key=lambda x:x[0],reverse=True) 

level = [0 for i in range(200)] 
#用来存储机器等级的数量，level[1]=1表示等级为1的机器有1个
for i in range(len(duty)):
    while j < len(machine) and machine[j][0]>=duty[i][0]:
        level[machine[j][1]]+=1
        j += 1
    for k in range(duty[i][1],200):
        (2799)# 从等级大于等于任务难度的机器中选择
        if level[k]:
            count += 1
            level[k] -= 1
            profile += 200*duty[i][0] + 3*duty[i][1]
            break
print(count,end=' ')
print(profile)
    

##感觉没有错呀，测试了一些还能过，方法上用的最简单的栈深度优先搜索，时间效率上不高，容易实现

n, m = input().split()
n, m = int(n), int(m)
zw_list=  []
for i in range(n):
    temp = [int(x) for x in input().split()]
    zw_list.append(temp)
xy_list = []
for i in range(m):
    temp = [int(x) for x in input().split()]
    xy_list.append(temp)

can_finish = [[] for i in range(n)]
for i in range(n):
    for j in range(m):
        if zw_list[i][0] >= xy_list[j][0] and zw_list[i][1] >= xy_list[j][1]:
            can_finish[i].append(j)
#print(can_finish)

stack = []
l_stack = []
start = 0
while len(can_finish[start]) == 0:
    start += 1
for i in range(len(can_finish[start])):
    stack.append(can_finish[start][i])
    l_stack.append(start)


temp_list = []
temp = []
while len(stack):
    s = stack.pop(-1)
    l = l_stack.pop(-1)
    temp.append(s)
    if l == n - 1:
        temp_list.append(temp)
        temp = []
    else:
        for j in range(len(can_finish[l+1])):
            stack.append(can_finish[l+1][j])
            l_stack.append(l+1)
#print(temp_list)
max_num = 0
max_temp_list = []
for temp in temp_list:
    temp = sorted(temp)
    num = 0
    for i in range(len(temp)-1):
        if temp[i] == temp[i + 1]:
            num  += 1
    mn = len(temp) - num
    if mn > max_num:
        max_num = mn
        max_temp_list = [temp]
    elif mn == max_num:
        max_temp_list.append(temp)
#print(max_temp_list)
max_score = 0
for temp in max_temp_list:
    score = 0
    for j in range(len(temp)):
        score += 200 * xy_list[temp[j]][0] + 3 * xy_list[temp[j]][1]
    if score > max_score:
        max_score = score
print(max_num, max_score)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + 10;
struct node {
    int x,y;
}e[maxn],f[maxn];
int cnt[105];
int cmp(node a ,node b){
    if(a.x == b.x)return a.y > b.y;
    return a.x > b.x;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++) scanf("%d%d",&e[i].x,&e[i].y);
    for(int i = 0;i < m;i++) scanf("%d%d",&f[i].x,&f[i].y);
    sort(e,e + n,cmp);
    sort(f,f + m,cmp);
    int num = 0;
    LL ans = 0;
    memset(cnt,0,sizeof(cnt));
    int i,j,k;
    for(i = 0,j = 0;i < m;i++){
        while(j < n && e[j].x >= f[i].x){
            cnt[e[j].y]++;
            j++;
        }
        for(k = f[i].y;k <= 100;k++){
            if(cnt[k]){
                num++;
                cnt[k]--;
                ans = ans + 200 * f[i].x +3 * f[i].y;
                break;
            }
        }
    }
    printf("%d %lld\n",num,ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + 10;
struct node {
    int x, y;
}e[maxn], f[maxn];  //定义两个结构数组
int cnt[105];
int cmp(node a, node b)
{
    if(a.x ==b.x)
        return a.y >b.y;
    return a.x > b.x;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
        scanf("%d%d", &e[i].x, &e[i].y);
    for(int i=0; i<m; i++)
        scanf("%d%d", &f[i].x, &f[i].y);
    sort(e, e+n, cmp);
    sort(f, f+m, cmp);
    int num = 0;
    LL ans = 0;
    memset(cnt, 0, sizeof(cnt));
    int i,j,k;
    for(i=0,j=0; i<m; i++)
    {
        while(j<n && e[j].x >= f[i].x){
            cnt[e[j].y]++;
            j++;
        }
        for(k=0; k<=100; k++)
        {
            if(cnt[k] && k>=f[i].y)
            {
                num++;
                cnt[k]--;
                ans += 200*f[i].x + 3*f[i].y;
                break;
            }
        }
    }
    printf("%d %lld\n", num, ans);
    return 0;
}

感觉没那么复杂，分为两块，一块求策略集，另一块求排列组合，组合的公式直接套就行，杨辉三角感觉有点过了。本人渣渣python，C和Java之类的不太会

# coding:utf-8
# 小Q的歌单
def match(a, x, b, y, k):
    get = []
    for i in range(x + 1):
        for j in range(y + 1):
            if i * a + j * b == k:
                get.append([i, j])
    return get


def c(i, j):
    a = 1
    b = 1
    tmp_i = i
    tmp_j = j
    while tmp_i >= 1:
        a = a * tmp_j
        b = b * tmp_i
        tmp_i = tmp_i - 1
        tmp_j = tmp_j - 1
    return a / b


k = int(raw_input().strip())
# print(c(2,4))
[a, x, b, y] = [int(i) for i in raw_input().strip().split()]
get = match(a, x, b, y, k)
if len(get) == 0:
    print 0
else:
    result = 0
    for i in get:
        result = result + c(i[0], x) * c(i[1], y)
    print result % 1000000007

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static class Pair {
        int time;
        int diff;

        public Pair(int time, int diff) {
            this.time = time;
            this.diff = diff;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int machineNum = sc.nextInt();
            int taskNum = sc.nextInt();
            Pair[] machines = new Pair[machineNum];
            Pair[] tasks = new Pair[taskNum];
            for (int i = 0; i < machineNum; i++) {
                machines[i] = new Pair(sc.nextInt(), sc.nextInt());
            }
            for (int i = 0; i < taskNum; i++) {
                tasks[i] = new Pair(sc.nextInt(), sc.nextInt());
            }
            Comparator<Pair> cmp = new Comparator<Pair>() {

                @Override
                public int compare(Pair p1, Pair p2) {
                    if (p1.time == p2.time) {
                        return p2.diff - p1.diff;
                    } else {
                        return p2.time - p1.time;
                    }
                }

            };
            Arrays.sort(machines, cmp);
            Arrays.sort(tasks, cmp);
            long sum = 0;
            int count = 0;
            int j = 0;
            int[] dp = new int[101];
            for (int i = 0; i < taskNum; i++) {
                while (j < machineNum && machines[j].time >= tasks[i].time) {
                    dp[machines[j].diff]++;
                    j++;
                }
                for (int k = tasks[i].diff; k < 101; k++) {
                    if (dp[k] != 0) {
                        dp[k]--;
                        sum += 200 * tasks[i].time + 3 * tasks[i].diff;
                        count++;
                        break;
                    }
                }
            }
            System.out.println(count + " " + sum);
        }
        sc.close();

    }

}

num_machine, num_task = map(int, input().split())
machine_list = []
task_list = []

for _i in range(num_machine):
    machine = list(map(int, input().split()))
    machine_list.append(machine)

for _j in range(num_task):
    task = list(map(int, input().split()))
    task_list.append(task)

machine_list.sort(reverse=True)  # 按时间成本从大到小排好
task_list.sort(reverse=True)  # 按时间成本从大到小排好


count = 0  # 完成工作计数
profit = 0  # 利润
level = [0]*101  # 等级列表
j = 0  # 机器计数

for i in range(num_task):
    while j < num_machine and machine_list[j][0] >= task_list[i][0]:
        level[machine_list[j][1]] += 1  # 机器的等级
        j += 1

    for k in range(task_list[i][1], 101):
        if level[k]:  # 如果为1，有机器可以用
            count += 1
            level[k] -= 1
            profit += task_list[i][0]*200 + task_list[i][1]*3
            break

print(count, profit)

求大神解答下面的 AC 代码原理

import sys


n_m = list(map(int, sys.stdin.readline().strip().split()))
n, m = n_m[0], n_m[1]
machines, tasks = [], []
for _ in range(n):
    machines.append(list(map(int, sys.stdin.readline().strip().split())))
for _ in range(m):
    tasks.append(list(map(int, sys.stdin.readline().strip().split())))

# 按照 time、level 来排序
machines.sort(key=lambda x: (x[0], x[1]), reverse=True)
tasks.sort(key=lambda x: (x[0], x[1]), reverse=True)

# level 到底用来存储什么？
level = [0 for _ in range(101)]
profit = 0
count = 0
j = 0
for task_time, task_level in tasks:
    while j < n and machines[j][0] >= task_time:
        # 这里为什么要一直加？
        level[machines[j][1]] += 1
        j += 1
    for i in range(task_level, 101):
        if level[i] > 0:
            count += 1
            # 这里为什么要一直减？
            level[i] -= 1
            profit += 200 * task_time + 3 * task_level
            break
print(count, profit)

def find_rightst(v, machines):
    left, right = 0, len(machines) - 1
    while left < right:
        mid = (left + right) // 2
        if machines[mid][1] < v:
            left = mid + 1
        elif machines[mid][1] > v:
            right = mid
        else:
            right -= 1
    return left
 
 
def max_value(machines, tasks):
    tasks.sort(key=lambda x: -(200 * x[0] + 3 * x[1]))
    machines.sort(key=lambda x:(x[1], x[0]))
    cnt, values = 0, 0
    visited = [0] * len(machines)
    for left in range(len(tasks)):
        for right in range(find_rightst(tasks[left][1], machines), len(machines)):
            if visited[right]:
                continue
            if tasks[left][1] > machines[right][1]&nbs***bsp;tasks[left][0] > machines[right][0]:
                continue
            else:
                visited[right] = 1
                cnt += 1
                values += tasks[left][0] * 200 + tasks[left][1] * 3
                break
    print(cnt, values)
 
if __name__ == '__main__':
    import sys
    [n, m] = [int(i) for i in sys.stdin.readline().strip().split()]
    machines, tasks = [], []
    for i in range(n):
        machines.append( [int(i) for i in sys.stdin.readline().strip().split()])
    for i in range(m):
        tasks.append( [int(i) for i in sys.stdin.readline().strip().split()])
    max_value(machines, tasks)

求解答，为什么暴力求解只能AC50%？？

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    
};
static int cmp(node t1,node t2)
{
    if(t1.x!=t2.x)
        return t1.x>t2.x;
    else
        return t1.y>t2.y;
 
}


int main(){
int n,m;
cin>>n>>m;
vector<node> jiqi(n);
for(int i=0;i<n;i++)
    cin>>jiqi[i].x>>jiqi[i].y;    //工作时间  等级
vector<node> task(m);
for(int i=0;i<m;i++)
    cin>>task[i].x>>task[i].y;  //任务时间  等级
sort(jiqi.begin(),jiqi.end(),cmp);
sort(task.begin(),task.end(),cmp);   
    
vector<vector<int>> temp(n,vector<int>(m,0));//机器完成任务
int count=0;
int sumvalue=0;
vector<bool> visitjiqi(n,false);
vector<bool> visitask(m,false);  
    
for(int i=0;i<n;i++) //机器
{
 int tempvalue=0;
 int index1=-1;
 int index2=-1;
   if(visitjiqi[i]==false)
   {
    for(int j=0;j<m;j++) //任务
    {
     if(visitask[j]==false)
     {
      if(jiqi[i].x>=task[j].x&&jiqi[i].y>=task[j].y)  
      {
      temp[i][j]=200*task[j].x+3*task[j].y;
      if(tempvalue<temp[i][j])
      {
       tempvalue=temp[i][j];
       index1=i;
       index2=j;
      }
      }
 }
    }  
 if(tempvalue!=0)
 {
     sumvalue+=tempvalue;
     count++;
     visitjiqi[index1]=true;
     visitask[index2]=true;
 }    
   }
 
}
cout<<count<<" "<<sumvalue<<endl;    
return 0;
}