1759 - 任务调度 X （无数据）
任务调度
【题目描述】
一个单位时间任务是个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其
中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,
结束于时间2;……。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下: 1.包含n个单位时间任务的集合S={1,2,……,n};
2.n个取整的期限d1,……,dn,(1≤d,≤n),任务i要求在di前完成;
3.n个非负的权(或罚款)w1,……,wn。如果任务i没在时间di之前结束,则导致罚款wi;
【输入】 输入第一行为N(N<=1000)，后面N行每行两个数，即为对应的di与wi
【输出】要求找出S的一个调度,使之最小化总的罚款。输出最小总罚款
题目输入
题目输出
输入/输出样例
题目输入
题目输出
C++解答
#include<cstdio> #include<algorithm> using namespace std; struct p { int num; int pr; }a[1005]; int comp(const p &a,const p &b) { if(a.pr<b.pr)return 1; else return 0; } int main() { int m,n; scanf("%d%d",&m,&n); for(int i=1;i<=n;++i) scanf("%d%d",&a[i].pr,&a[i].num); sort(a+1,a+n+1,comp); int i=0,ans=0; while(m>0) { ++i; if(m>=a[i].num) { ans+=a[i].num*a[i].pr; m-=a[i].num; continue; } if(m<=a[i].num) { ans+=m*a[i].pr; m=0; continue; } } printf("%d",ans); return 0; }