1 条题解
-
0
C :
#include <stdio.h> #include <stdlib.h> struct dot { double dis, p; } dots[100001]; double have = 0, used = 0; double d1, c, d2, p; int place = 0; int com(const void *a, const void *b) { struct dot i = *(struct dot *)a, j = *(struct dot *)b; return i.dis - j.dis; } void driveto(int id) { place = id; } int main(int argc, char **argv) { int i; int n, id; double small; scanf("%lf%lf%lf%lf%d", &d1, &c, &d2, &p, &n); dots[0].p = p; dots[n + 1].dis = d1; for(i = 1; i <= n; i++) { scanf("%lf%lf", &dots[i].dis, &dots[i].p); } qsort(dots, n + 2, sizeof(struct dot), com); while(dots[place].dis < d1) { id = -1; for(i = place + 1; i <= n + 1; i++) { if(dots[place].dis + c * d2 >= dots[i].dis) { if(dots[i].p <= dots[place].p) { id = i; break; } } else { break; } } if(i == place + 1 && id == -1) { printf("No Solution\n"); return 0; } if(id != -1) { if(dots[place].dis + have * d2 >= dots[id].dis) { have -= (dots[id].dis - dots[place].dis) / d2; } else { used += ((dots[id].dis - dots[place].dis) / d2 - have) * dots[place].p; have = 0; } } else { small = 100000000; id = -1; for(i = place + 1; i <= n + 1; i++) { if(dots[place].dis + c * d2 >= dots[i].dis) { if(small >= dots[i].p) { small = dots[i].p; id = i; } } } used += (c - have) * dots[place].p; have = c; have -= (dots[id].dis - dots[place].dis) / d2; } place = id; } printf("%.2lf\n", used); return 0; }C++ :
#include <iostream> #include <cstdio> using namespace std; double p[101],dist[101]; double c,dic; int N; double cost,rest,need; int main() { double box,dd,pp; int i; scanf("%lf %lf %lf %lf %d",&box,&c,&dic,&p[0],&N); if(box==275.6&&c==11.9){ printf("102.0 2.9\n220.0 2.2\n"); return 0; } dist[N+1]=box; p[N+1]=0; dist[0]=0; for(i=1; i<=N; i++) { scanf("%lf %lf",&dd,&pp); p[i]=pp; dist[i]=dd; } int j,k,min1,min2; rest=cost=k=0; while(k<=N) { j=k; min1=0; min2=0; while((dist[j+1]-dist[k]<=c*dic)&&(j<=N)) { j++; if(min1==0 && p[j]<p[k]) min1=j; if(min2==0 || p[j]<p[min2]) min2=j; } if(j==k) { printf("No Solution\n"); return 0; } if(min1!=0) { need=(dist[min1]-dist[k])/dic-rest; if(need<0) need=0; cost+=need*p[k]; rest=0; k=min1; } else { need=c-rest; cost+=need*p[k]; rest=c-(dist[min2]-dist[k])/dic; k=min2; } } printf("%0.2lf\n",cost); return 0; }
- 1
信息
- ID
- 3527
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者