「NOIP模拟赛」肥得更高

自2009年以来，A、B站的历史就已经步入了农业变革的黎明期。
在两站的娱乐及音乐区，金坷垃制造业早已得到长足的发展，甚至有些地方还出现了坷垃翻唱的萌芽。
新兴肥料人开始走上历史的舞台。
他们需要新的意识形态，来为他们所追求的肥料辩护；
他们需要新的理念、新的手段，来为金坷垃的生产提供支持。
这样，一种崭新的肥料精神就诞生了。
肥料复兴，是反对肥料粗制滥造，追求创新的新肥料文化的运动。
它必将成为推动金坷垃走得更远、飞得更高的重要力量。

现在，你有n亩的小麦地需要增产，你拥有一些金坷垃，但是金坷垃极其稀少，掺肥料也只够你撒K次。

众所周知，金坷垃能激活土壤深处的氮磷钾，同一块地可以撒多次肥料，但是效果是有略微衰减的。

实地考察后你发现，第i亩土地第x次撒肥料增产a[i]-x+1公斤。

hzwer将代替你去撒肥料，但是他是个蒟蒻，完全不动大脑，所以你想知道如果他随机撒肥料，最坏情况下小麦将增产多少，最好情况下将增产多少？(他最多只会对第i亩地撒肥料a[i]次)

第一行两个整数n，K

第二行n个整数，第i个整数为a[i]

输出最大值，最小值，空格隔开

输入　 [复制]

5 10
10 3 3 1 2

输出

58 26

对于30%的数据n，k<=1000

对于70%的数据n，k<=200000

对于100%的数据n，k，a[i]<=1000000

题解

显然每次都取a[i]的最大值/最小值，并更新a[i]即可

用数据结构维护这一操作。。得分看常数

事实上用v[i]记录权值为i的个数，然后for乱搞就可以了。。。不过我懒得写了。。。

其它乱搞做法能获得不同的分数

提供一种50分解法

排序后

最小值，从左依次取到0

最大值，一直取最右的那个，如果它变得比前面的小就交换位置。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[1000005],t[1000005];
long long mn,mx;
int main()
{
    m=read();n=read();
    for(int i=1;i<=m;i++)a[i]=read();
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)t[i]=a[i];
    int now=1;
    for(int i=1;i<=n;i++)
    {
        mn+=t[now];
        t[now]--;if(!t[now])now++;
    }
    for(int i=1;i<=m;i++)
        t[i]=a[i];
    for(int i=1;i<=n;i++)
    {
        mx+=t[m];
        t[m]--;
        int k=m;
        while(t[k]<t[k-1])swap(t[k],t[k-1]),k--;
    }
    printf("%lld %lld",mx,mn);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[1000005],t[1000005];

long long mn,mx;

int main()

{

m=read();n=read();

for(int i=1;i<=m;i++)a[i]=read();

sort(a+1,a+m+1);

for(int i=1;i<=m;i++)t[i]=a[i];

int now=1;

for(int i=1;i<=n;i++)

{

mn+=t[now];

t[now]--;if(!t[now])now++;

}

for(int i=1;i<=m;i++)

t[i]=a[i];

for(int i=1;i<=n;i++)

{

mx+=t[m];

t[m]--;

int k=m;

while(t[k]<t[k-1])swap(t[k],t[k-1]),k--;

}

printf("%lld %lld",mx,mn);

return 0;

}

把最大值的做法改成pq维护的话就能随便水过了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
int a[1000005];
priority_queue<int> q;
ll mx,mn;
int main()
{
    n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read(),q.push(a[i]);
	sort(a+1,a+n+1);
	int now=1;
	for(int i=1;i<=m;i++)
	{
		int t=q.top();q.pop();
		mx+=t;
		q.push(t-1);
		while(!a[now])now++;
		mn+=a[now];a[now]--;
	}
	printf("%lld %lld",mx,mn);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<queue>

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[1000005];

priority_queue<int> q;

ll mx,mn;

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read(),q.push(a[i]);

sort(a+1,a+n+1);

int now=1;

for(int i=1;i<=m;i++)

{

int t=q.top();q.pop();

mx+=t;

q.push(t-1);

while(!a[now])now++;

mn+=a[now];a[now]--;

}

printf("%lld %lld",mx,mn);

return 0;

}

hzwer.com _ Home | http://hzwer.com

背景

描述

输入格式

输出格式

样例数据 1

备注

分类目录

热门文章

Myfriends

近期评论