Call对应函数式:K×X-P×X-C
Put对应函数式:P×X-K×X-C
分析:
1.建立一个结构体,存储类型type(Call或Put),以及C,P,K。
2.输入完后,按P进行从小到大排序。
3.排完序后,每个区间段都已经分好了,接下来主要思考一下,对应区间的a,c的值
3.1,假设我们现在的价格为X,那么,此时我们可以执行比X小的所有Call的指令,以及比X大的所有Put的指令。
3.2,因为X是从0开始逐渐递增的,因此,一开始X可以执行所有的Put的指令,因此一开始a= - (Put_K1+Put_K2+…),而c=Put_K1×Put_P1+Put_K2×Put_P2+… - (C1+C2+…)(因为所有的指令都要一个cost,因此要减去C的总和)。
3.3,当X逐渐增加时,会经过某条指令,当它为Call时,a+K,,c-P×K,当它为Put时,a+K,c-P×K,因此,无论是什么指令,都要进行a+K,,c-P×K的操作。
注意:某些Put或者Call的P有可能会相同,这时要进行统一处理,会在代码中体现。
代码如下:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
struct name
{
char type[10];
ll c,p,k;
}n[maxn];
bool cmp(name x,name y)
{
return x.p<y.p;
}
void print(ll a,ll c) //打印出a,c
{
if(a==0)
printf("b=%lld\n",c);
else
{
if(c==0)
printf("b=%lld*x\n",a);
else if(c>0)
printf("b=%lld*x+%lld\n",a,c);
else printf("b=%lld*x%lld\n",a,c);
}
}
int main()
{
int T,N,i,j,kase=1;
ll sum1,sum2,sum3,a,c,temp; //sum1记录所有c的和,sum2,sum3记录所有PUT的k,p×k的和。
scanf("%d",&T);
while(T--)
{
sum1=sum2=sum3=a=c=0;
scanf("%d",&N);
for(i=1;i<=N;i++)
{
scanf("%s%lld%lld%lld",n[i].type,&n[i].c,&n[i].p,&n[i].k);
sum1+=n[i].c;
if(strcmp(n[i].type,"Put")==0)
{
sum2+=n[i].k;
sum3+=n[i].p*n[i].k;
}
}
sort(n+1,n+1+N,cmp);
a=-sum2;c=sum3-sum1;
printf("Case #%d:\n",kase++);
printf("[0,%lld] ",n[1].p);
print(a,c);
temp=n[1].p;
for(i=1;i<=N;i++)
{
for(j=i;j<=N;j++)
{
if(temp==n[j].p)
{
i=j;
a+=n[j].k;
c-=n[j].p*n[j].k;
}
else
{
if(j<=N)
temp=n[j].p;
break;
}
}
if(i!=N)
printf("[%lld,%lld] ",n[i].p,n[j].p);
else printf("[%lld,...] ",n[i].p);
print(a,c);
}
}
return 0;
}
TIPS:代码中统一处理P相同的部分要多注意,熟练起来。