Analyzing Polyline CodeForces - 195D

2018-06-17 21:46:02来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Analyzing Polyline CodeForces - 195D

题意:有n个函数,第i个函数yi(x)=max(ki*x+bi,0)。定义函数s(x)=y1(x)+y2(x)+...+yn(x)。显然函数s的图像是一条折线。求折线上有多少个转折点。

方法:对于每一个函数yi(x)的图像,如果ki等于0,那么没有转折点,否则都有一个转折点,就是在点(-bi/ki,0)处(也就是使得函数值恰好为max(0,0)=0)。如果函数yi和yj有两个不同的转折点,那么它们的和的函数图像显然就会有两个转折点;如果函数yi和yj有两个相同的转折点,那么它们和的函数图像显然只会有一个转折点。对于函数s也是类似的,其转折点个数就是y1到yn中不同的转折点个数,也就是不同的-bi/ki的个数。

 1 #include<cstdio>
 2 #include<set>
 3 using namespace std;
 4 set<long double> s;
 5 int n,k,b;
 6 int main()
 7 {
 8     int i;
 9     scanf("%d",&n);
10     for(i=1;i<=n;i++)
11     {
12         scanf("%d%d",&k,&b);
13         if(k!=0)    s.insert((-(long double)b)/k);
14     }
15     printf("%d",s.size());
16     return 0;
17 }

http://blog.csdn.net/dlpf_c/article/details/76012830

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++ 作业 10月13日 进制转换最简单方法,控制c++输出格式方法 教

下一篇:HDU_6043_KazaQ&#39;s Socks