社区讨论
75pts求助,Subtask5过不去
P1016[NOIP 1999 普及组/提高组] 旅行家的预算参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2rfocx
- 此快照首次捕获于
- 2023/10/23 18:33 2 年前
- 此快照最后确认于
- 2023/10/23 18:33 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int X=0;
bool flag=1;
char ch=getchar();
while (ch<'0' || ch>'9')
{
if (ch=='-')
flag=0;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
X=(X<<1)+(X<<3)+ch-'0';
ch=getchar();
}
if (flag)
return X;
return ~(X-1);
}
int n;
double c,d1,d2,p;
int now=0,ret=114514;
double ans=0,maxn,res=0;
struct station
{
double d,p;
}a[10];
bool cmp(station a,station b)
{
return a.d<b.d;
}
int solve(int x)
{
int k=ret;
for (int i=x+1;i<=n && a[i].d-a[x].d<=maxn;i++)
{
if (a[i].p<a[x].p)
{
ans+=(a[i].d-a[x].d)/d2*a[x].p;
res=0;
return i;
}
if (k==ret || a[i].p<a[k].p)
k=i;
}
if (d1-a[x].d<=maxn)
{
ans+=(d1-a[x].d)/d2*a[x].p;
return ret;
}
if (a[x+1].d-a[x].d>maxn)
{
cout<<"No Solution";
return -1;
}
ans+=c*a[x].p;
res+=(maxn-(a[k].d-a[x].d));
return k;
}
signed main()
{
cin>>d1>>c>>d2>>p>>n;
maxn=c*d2;
for (int i=1;i<=n;i++)
cin>>a[i].d>>a[i].p;
a[0].d=0;
a[0].p=p;
sort(a,a+n,cmp);
while (now!=ret)
{
now=solve(now);
if (now==-1)
return 0;
}
cout<<fixed<<setprecision(2)<<ans;
return 0;
}
/*
* things to check
* 1. int overflow or long long memory need
* 2. recursion/array/binary search/dp/loop bounds
* 3. precision
* 4. special cases(n=1,bounds)
* 5. delete debug statements
* 6. initialize(especially multi-tests)
* 7. = or == , n or m ,++ or -- , i or j , > or >= , < or <=
* 8. keep it simple and stupid
* 9. do not delete, use // instead
* 10. operator priority
* 11. is there anything extra to output?
* 12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
* 13. submit ONCE, AC once. submit twice, WA forever
* 14. calm down and you'll get good rank
* 15. even a bit wrong scores zero
* 16. ...
**/
Subtask5 input:
475.6 11.9 27.4 14.98 6
102.0 9.99
220.0 13.29
256.3 14.79
275.0 10.29
277.6 11.29
381.8 10.09
Subtask5 output:
192.15
My output:
209.19
回复
共 2 条回复,欢迎继续交流。
正在加载回复...