首页 > 其他 > 详细

【2019中国大学生程序设计竞赛-女生专场】C - Function

时间:2019-10-14 22:29:44      阅读:98      评论:0      收藏:0      [点我收藏+]

原题

技术分享图片

技术分享图片

 

 

韦神提供的思路orz

首先一个显然的性质,所有的c可以提出来,方程变成ax^2+bx的形式

因为x的值是离散的,而m的值又不大

所以一开始让x都为1(注意!x是正整数),然后每次挑一个x让他加一

这样做怎么保证正确?

注意二次函数的性质,由于a>=1,当x递增时斜率,函数值的变化量是递增的

可以贪一个

每次去变化率最小的那个方程,让它的x加一

现在不取,后边也不会更优,所以正确

变化率相同时并不需要比较函数形状

因为由变化率递增的性质,就算取了较坏的函数,下一步还是取较好函数的相同变化量,然后再下一步必定会取到较好函数

 

代码:

技术分享图片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL long long
 8 int rd(){int z=0,mk=1;  char ch=getchar();
 9     while(ch<0||ch>9){if(ch==-)mk=-1;  ch=getchar();}
10     while(ch>=0&&ch<=9){z=(z<<3)+(z<<1)+ch-0;  ch=getchar();}
11     return z*mk;
12 }
13 struct nds{LL x;  int y;}hp[110000];  int sz=0;
14 int n,m;
15 LL a[110000],b[110000],c[110000];
16 int d[110000];
17 LL cclt(LL x,int y){
18     return x*x*a[y]+x*b[y];
19 }
20 void ist(nds x){
21     hp[++sz]=x;
22     for(int i=sz;i>1 && hp[i].x<hp[i>>1].x;i>>=1)  swap(hp[i],hp[i>>1]);
23 }
24 void pp(){
25     swap(hp[1],hp[sz--]);
26     for(int i=1;;){
27         int mn=hp[i].x,mnid=i;
28         if((i<<1)<=sz && hp[i<<1].x<mn)  mn=hp[i<<1].x,mnid=(i<<1);
29         if((i<<1|1)<=sz && hp[i<<1|1].x<mn)  mn=hp[i<<1|1].x,mnid=(i<<1|1);
30         if(i==mnid)  break;
31         swap(hp[i],hp[mnid]);
32         i=mnid;
33     }
34 }
35 void prvs(){
36     sz=0;
37 }
38 int main(){
39     //freopen("ddd.in","r",stdin);
40     while(scanf("%d%d",&n,&m)!=EOF){
41         prvs();
42         for(int i=1;i<=n;++i)  a[i]=rd(),b[i]=rd(),c[i]=rd();
43         LL bwl=0;
44         for(int i=1;i<=n;++i){
45             d[i]=1;
46             ist((nds){cclt(d[i]+1,i)-cclt(d[i],i),i});
47             bwl+=cclt(d[i],i)+c[i];
48         }
49         for(int i=n+1;i<=m;++i){
50             LL mn=hp[1].x;  int mnid=hp[1].y;
51             ++d[mnid];
52             pp();
53             ist((nds){cclt(d[mnid]+1,mnid)-cclt(d[mnid],mnid),mnid});
54             bwl+=mn;
55         }
56         printf("%lld\n",bwl);
57     }
58     return 0;
59 }
View Code

 

【2019中国大学生程序设计竞赛-女生专场】C - Function

原文:https://www.cnblogs.com/cdcq/p/11674305.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!