17年广东省赛——C,Stokpie(思维)

news/2024/8/26 15:08:29 标签: 思维, 代码能力

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相同的部分要多注意,熟练起来。


http://www.niftyadmin.cn/n/943255.html

相关文章

BZOJ 4244 邮戳拉力赛

题意&#xff1a; 思路&#xff1a; 参考博客 https://blog.csdn.net/forever_shi/article/details/84931438 /**************************************************************Problem: 4244User: fufckLanguage: CResult: AcceptedTime:8364 msMemory:72076 kb *********…

bzoj 1066: [SCOI2007]蜥蜴

Description 在一个r行c列的网格地图中有一些高度不同的石柱&#xff0c;一些石柱上站着一些蜥蜴&#xff0c;你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1&#xff0c;蜥蜴的跳跃距离是d&#xff0c;即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石…

组合数的一些模板(好用)

一、 ll qpow(ll a,ll b,ll p) {ll ret1;a%p;while(b){if(b&1) retret*a%p;b/2;aa*a%p;}return ret; } 二、Lucas ll lucas(ll n,ll m,ll p) {if(m0) return 1;return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p; } 三、C(n,m) 方案一&#xff1a;&#xff08;直接算&#xff0…

bzoj 1934: [Shoi2007]Vote 善意的投票

Description 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说&#xff0c;这个问题并不是很重要&#xff0c;于是他们决定发扬谦让精神。虽然每个人都有自己的主见&#xff0c;但是为了照顾一下自己朋友的想法&#xff0c;他们也可以投和自己本来意愿相反的票。我…

bzoj 1706: [usaco2007 Nov]relays 奶牛接力跑

Description FJ的N(2 < N < 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 < T < 100)条跑道上。 农场上的跑道有一些交汇点&#xff0c;每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 < I1_i < 1,0…

杭电ACM——1247,Hat’s Words(Trie树)

这道题是有问题的&#xff0c;一个单词是可以被另外一个单词拼接两次得到的&#xff0c;如ab&#xff0c;abab&#xff0c;输出是abab&#xff0c;然而原题确指明&#xff0c;某个单词当且仅当是另外字典里的两个单词拼接的&#xff0c;才是一个hat’s word&#xff0c;实际上这…

bzoj 1001: [BeiJing2006]狼抓兔子

Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到&#xff0c;但抓兔子还是比较在行的&#xff0c;而且现在的兔子还比较笨&#xff0c;它们只有两个窝&#xff0c;现在你做为狼王&#xff0c;面对下面这样一个网格的地形&#xff1a; 左上角点…

杭电ACM——2533,N皇后问题(搜索)

突破口&#xff1a; N*N的棋盘放置N个皇后&#xff0c;因为皇后的特性&#xff0c;合法的放置方法中每行&#xff08;每列&#xff09;必定有一个皇后&#xff0c;因此我们可以先搜索第1行可以放置的位置&#xff0c;再逐步搜索第2行&#xff0c;直到第N行。而不用去穷举第一个…