Commando War-uva 贪心

本文主要是介绍Commando War-uva 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大意：给你N个任务，你交代他需要J时间，完成他需要B时间，问怎么搭配可以使全部问题完成时话的时间最少

思路：贪心算法，先做完成时间长的，完成时间相同的话先做交代时间长的，用了一下结构体二级快排

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 1000 + 10
struct Time
{int talk;    /*讲述的时间*/int finsh;    /*完成的时间*/
};
int cmp(const void *a,const void *b)
{struct Time*c=(Time*)a;struct Time*d=(Time*)b;if(c->finsh!=d->finsh)return ((d->finsh)-(c->finsh));elsereturn ((d->talk)-(c->talk));
}
int main()
{int cases,N;struct Time Mission[MAX_SIZE];for(cases=1;scanf("%d",&N);cases++){int Alltime=0;if(!N)  break;for(int i=0;i<N;i++)scanf("%d%d",&Mission[i].talk,&Mission[i].finsh);/*按照完成时间从大到小排序，如果完成时间相同讲述时间排序*/qsort(Mission,N,sizeof(Mission[0]),cmp);int t1=Mission[0].finsh;int t2=0;for(int i=1;i<N;i++){int temp;t2+=Mission[i].talk;temp=t2+Mission[i].finsh-t1;if(temp<0)temp=0;t1+=temp;}printf("Case %d: %d\n",cases,t1+Mission[0].talk);}return 0;
}

这篇关于Commando War-uva 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---