贪心算法python？水题 模拟计算

//#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 99999;
int m1,m2;
int r1,r2,r3;int main()
{while(cin>>m1>>m2){r1=r2=r3=0;string s;cin>>s;for(int i=0; i<s.size(); i++){if(s[i]=='A'){r1=m1;}else if(s[i]=='B'){r2=m2;}else if(s[i]=='C'){m1=r3;}else if(s[i]=='D'){m2=r3;}else if(s[i]=='E'){r3=r1+r2;}else if(s[i]=='F'){r3=r1-r2;}}printf("%d,%d\n",m1,m2);}return 0;
}

水题 要尽可能少用板子 所以由大到小排序，先使用大的

//#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 99999;int l;
int n;bool cmp(int a,int b)
{return a>b;
}
int main()
{while(scanf("%d%d",&l,&n)==2/*cin>>l>>n*/){int cnt=0; int cur=0;int *a=new int[n];for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n,cmp);for(int i=0;i<n;i++){if(cur>=l) break;cur+=a[i];cnt++;}if(cur<l) printf("impossible\n");else printf("%d\n",cnt);}return 0;
}

• 贪心策略： 先完成扣分多的作业；如果扣分相同，先完成ddl早的
• 对于一个作业越晚做越好，可以腾出时间做前面的作业，so，从最晚的ddl向前倒推找到没有被分配上作业的日子。如果没有的话，说明这一个作业无法完成，需要扣分。

//#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 99999;struct work
{
//	int t;int ddl;int cost;
};
bool cmp(work a, work b)//优先考虑ddl紧张的先做是错误思路
{if(a.ddl != b.ddl)return a.ddl<b.ddl;return a.cost>b.cost;
}
bool cmp2(work a,work b)//应该优先考虑扣分多得先做
{if(a.cost==b.cost)return a.ddl<b.ddl;elsereturn a.cost>b.cost;
}
int T;
int n;
work a[maxn];
bool vis[maxn];int main()
{cin >> T;while(T--){memset(vis,0,sizeof(vis));//初始化都没有被安排作业标记为0cin >> n;for(int i = 0; i < n; i++) cin >> a[i].ddl;for(int i = 0; i< n; i++) cin >> a[i].cost;sort(a,a+n,cmp2);//以分数为降序排序,先做分数扣得多的 int anscost=0;for(int i=0; i<n; i++)//有n件作业{int t = a[i].ddl;//从截止日期往前推，完成该项作业的日子离截止日期越近越好 while(t){if(vis[t]==0){vis[t]=true;//该天被安排写作业标记break;}elset--;//继续往前推 if(t==0)anscost+=a[i].cost;//已经不能再往前推了，这时一定会被扣分}}printf("%d\n",anscost);}return 0;
}