本文主要是介绍08年东莞特长生 工作,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
08年东莞特长生 工作
Time Limit:1000MS Memory Limit:65536K
Total Submit:39 Accepted:20
Description
这次故事的主角是HG!转眼4年过去了,HG本科毕业了,于是找了份工作。每天HG会收到一份任务清单,清单上列出了n个可能需要他完成的任务。每个任务包含3个信息:Ti、Ai、Bi,Ti表示完成此任务需要的时间,Ai表示此任务的到达时间,Bi表示此任务的最晚完成时间。在某一时刻若HG手上没有任务,那么他可以选择一个已经到达且还能够在Bi时刻之前(或者恰好在Bi时刻)完成的任务来做。
由于HG有点懒(纯属虚构:D),他想尽量少的减少他的总工作时间,但是他不能在可以做任务的时候故意不做(这样会被炒鱿鱼的>_<),那么他该如何挑选任务来做呢?
你的任务就是求出HG的最少工作时间(即总共有多少时间HG在做任务)。
Input
第一行一个整数n表示任务数。
以下n行,每行三个整数Ti,Ai,Bi。(n<=1000,0<=Ai,Bi<=1500,Ti>=1)
Output
输出仅一个数,即最少工作时间。
Sample Input
3
15 0 25
50 0 90
45 15 70
Sample Output
50
Hint
Ti>=1,0<=Ai,Bi<=1200;
30%的数据满足n<=5;60%的数据满足n<=500;100%的数据满足n<=1000。
输入数据保证Bi-Ai要大于等于Ti,且小于2Ti。
这里写代码片
#include<cstdio>
using namespace std;
int n,m;
int a[3001],b[3001],t[3001],f[3001];
bool check;
void qsort(int l,int r){if(l>=r)return;int i=l,j=r,m=a[(l+r)/2];while(i<j){while(a[i]<m)i++;while(a[j]>m)j--;if(i<=j){int r=a[i];a[i]=a[j];a[j]=r;r=b[i];b[i]=b[j];b[j]=r;r=t[i];t[i]=t[j];t[j]=r;i++;j--;}}qsort(l,j);qsort(i,r); }
int main(){//freopen("work.in","r",stdin);//freopen("work.out","w",stdout);int start=100000;int last=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&t[i],&a[i],&b[i]);if(last<b[i])last=b[i];if(start>a[i])start=a[i]; }for(int i=1;i<=3001;i++)f[i]=-1;qsort(1,n);f[start]=0;for(int i=start;i<=last;i++){if(f[i]!=-1){check=0;for(int j=1;j<=n;j++){if(i>=a[j]&&i+t[j]<=b[j]){check=1;if(f[i+t[j]]==-1||f[i]+t[j]<f[i+t[j]])f[i+t[j]]=f[i]+t[j];}// if(i<a[i])break; }if(!check){if(f[i+1]==-1||f[i+1]>f[i])f[i+1]=f[i];} }}printf("%d",f[last]); }
这篇关于08年东莞特长生 工作的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!