社区讨论

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 条回复,欢迎继续交流。

正在加载回复...