公交车在第1分钟从1号景点出发，第2分钟到达2号景点，第5分钟从2号景点出发，第7分钟到达3号景点。 第1个旅客旅行时间7 - 0 = 7分钟； 第2个旅客旅行时间2 - 1 = 1分钟； 第3个旅客旅行时间7 - 5 = 2分钟。 总时间7 + 1 + 2 = 10分钟。 数据范围：
对于10%的数据，k = 0； 对于20%的数据，k = 1；
对于40%的数据，2 ≤ n ≤ 50，1 ≤ m ≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ Ti ≤ 500；
对于60%的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；
对于100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 100,000。
---------------------------------------------------------------- 正解=贪心
设 time[i] 为到达第 i 的时间，
设 last[i] 为出现在第 i 点的最后一个游客的时间，
题目求所有乘客等待时间和，即ans=（time[i]-T[i]）（1<=i<=m） T[i]为定值，那应使time的值尽量小。
显然time[i]=max(time[i-1],last[i-1])+d[i-1]; 由于使用一个加速器后可能会是多个time减少，
last[i]则就成为了一个限制条件（使time[i]的减少无意义），
在一条路径使用加速器后会对后面多个time（不是所有）产生影响， 设在 i 放一个加速器可影响到的点数的数量为f[i]， 设 sum 为记录在 i 之前及 i 已下车的人数，
则如果在i点使用加速器后，可影响的人数为sum[f[i]+i]-sum[i], 也就是在 i 到 f[i]+i 之间要到达下一个点的人数 便可以此贪心，
每使用一次加速器后（减少d），重新再算 time 和 f，在从中选出sum[f[i]+i]-sum[i]中最大的，在 i 用加速器 Ps. 100000*1000的复杂度居然能过- = 代码如下：
1 #include
7 #define INF 999999999999 8 #define LL long long
9 #define Max(x,y) if(y>x) x=y; 10 #define N 10010
11 //using namespace std ;
12 int f[N],sum[N],dis[N],up[N],down[N],b[N],last[N],time[N]; 13 int n,m,k,total,ans; 14 int max(int a,int c){
15 return a > c ? a : c; 16 }
17 int main(){
18 scanf(\,&n,&m,&k);
19 for(int i=1;i< n;i++) scanf(\,&dis[i]); 20 for(int i=1;i<=m;i++) { 21 int a,c;
22 scanf(\,&c,&a,&b[i]); 23 total+=c; 24 ++up[a];
25 ++down[b[i]]; 26 Max(last[a],c);
27 for(int j=b[i];j<=n;j++) sum[j]++; 28 }
29 while(k--){
30 for(int i=2;i<=n;i++)
31 time[i]=max(time[i-1],last[i-1])+dis[i-1]; 32 f[n]=0;
33 for(int i=n-1;i;i--) 34 if(time[i+1]>last[i+1]) 35 f[i]=f[i+1]+1; 36 else f[i]=1; 37
38 int maxval=-1,maxpos=0; 39
40 for(int i=1;i 41 if(dis[i]&&f[i]&&sum[f[i]+i]-sum[i]>maxval){ 42 maxval=sum[f[i]+i]-sum[i]; 43 maxpos=i; 44 } 45 if(maxpos) --dis[maxpos]; 46 } 47 for(int i=2;i<=n;i++) 48 time[i]=max(time[i-1],last[i-1])+dis[i-1]; 49 for(int i=1;i<=m;i++) ans+=time[b[i]]; 50 printf(\,ans-total); 51 } 2013年10月17日 noip2008 双栈排序 描述 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。 操作a 如果输入序列不为空，将第一个元素压入栈S1 操作b 如果栈S1不为空，将S1栈顶元素弹出至输出序列 操作c 如果输入序列不为空，将第一个元素压入栈S2 操作d 如果栈S2不为空，将S2栈顶元素弹出至输出序列 如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。 将(1,3,2,4)排序的操作序列： Tom希望知道其中字典序最小的操作序列是什么。 格式 输入格式 第一行是一个整数n。 第二行有n个用空格隔开的正整数，构成一个1~n的排列。 输出格式 输出文件共一行，如果输入的排列不是“可双栈排序排列”，输出数字0； 否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 数据范围 30%的数据满足： n<=10 50%的数据满足： n<=50 100%的数据满足： n<=1000 ------------------------------------------------------------------------ 正解=图匹配Orz。。 先考虑单栈排序 显然这是个由下到上的递减栈。 能单栈排序的情况： 不存在 （i 当 j 要进栈时，i 必须出栈，但 k 又必须在 i 前出栈，显然不可以- = 充分性： 当 i A ： 当 v[i]>v[j] 时 i ，j可以同时在栈中，无论v[k]的值如何，都能进行排序（显然） B： 当 v[i] 所以显然除 （i 其实也可以像ak大神（Orz）一样，拿1 2 3举例证明，虽不怎么全面，但很好理解。 考虑完单栈回到双栈排序 就像归并一样，两个都能排序，那合起来也能排序。 如果存在（i 做一遍染色即可，出现非法情况（同一点染上不同颜色）就无解。 让完后做一个简单的字典序最小进栈出栈操作,记下当前要出栈的数，然后依题意搞之即可（令人蛋疼- =）。 代码如下： 1 #include 8 #define INF 99999999 9 #define LL long long 10 using namespace std; 11 int col[1001],next[10010],last[10010],s[10010],T,n,v[1001],K[1001],ans[3000]; 12 stack 13 void addedge(int x,int y){ 14 next[++T]=last[x]; last[x]=T; s[T]=y; 15 next[++T]=last[y]; last[y]=T; s[T]=x; 16 } 17 void DFS(int now,int c){ 18 if(!col[now]) col[now]=c; 19 else if(col[now]!=c){ 20 printf(\); 21 exit(0); 22 } else return ;
相关推荐：
loading