A-Meditation

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Luna had a stressful day and she wants to do a meditation routine that relaxes her well. Luna's routines are more or less relaxing and to determine how relaxing a routine is, Luna computes its score: the higher the score, the more relaxing it is!

Luna has graded each of the \(n\) exercises with a positive integer and the score of a routine is simply the sum of the grades of its individual exercises. She gives you her list of graded exercises and asks you what is the maximal grade of a routine composed of \(k\) different exercises.

输入描述

The first line of the input contains two space-separated integers:\(n\) and \(k\).
The \(n\) following lines each contain a single integer, the \(i+1-th\) line containing the grade \(g_i\) of the \(i\)-th exercise.

输出描述

The output should contain a single line with a single integer: the maximal score of a routine composed of \(K\) different exercises.

示例1

输入

5 3
10
22
7
3
10

输出

42

说明

We select the exercises 1, 2 and 5 which gives a total score of \(10+22+10=42\).

备注

\(1≤k≤n≤100000\)
\(0\leq g_{i}\leq 10\,000\)

题目大意

给出\(n\)个数，求其中\(k\)个相加的最大值是多少？

cpp

//直接排序，去末尾k个数相加即为答案
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000005];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	long long sum=0;
	for(int i=n;i>=n-k+1;i--) sum+=a[i];
	cout<<sum<<endl;
	return 0;
}

---

B-Rounds

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

The popular PefectSharp online group gathers fans of workouts and healthy lifestyle all over the world. Every group member has managed to gain a certain amount of credits for the trendy MV03 online sports platform, giving them access to various workout and relaxation resources.

The amount of credits owned may however largely differ from one person to the other. Since PefectSharp members value sharing and solidarity, they decide to redispatch credits by playing the following game:

The \(N\) group members are numbered from \(1\) to \(N\) and the game comprises \(k\) rounds, for some integer \(k\) such that \(1 \leq k \leq N\). During the \(i\)-th round of the game, all members except member \(i\) give \(S\) credits to member \(i\). The game may end after any round, and its outcome will be the minimum amount of credits held by a member of the group after that round.

Your task is to figure out the maximum possible game outcome, across all possible game endings.

输入描述

The first line of the input contains two integers \(N\) and \(S\).
Each of the \(N\) following lines contains a single integer, the \((i + 1)\)-th line containing the amount of credits Ciinitially owned by member \(i\).

输出描述

The output should contain a single integer value \(C\) corresponding to the maximum possible game outcome.

示例1

输入

3 10
24
42
38

输出

28

说明

The game proceeds as follows:
After round \(1\) the amounts of credits held are \(44, 32, 28\) and the minimum is \(28\).
After round \(2\) the amounts of credits held are \(34, 52, 18\) and the minimum is \(18\).
After round \(3\) the amounts of credits held are \(24, 42, 38\) and the minimum is \(24\).
The best possible outcome is therefore \(28\), which corresponds to ending the game after round \(1\).

备注

\(1≤N≤100000\)
\(1\leq S \leq 100\,000\,000\)
for all,\(1\leq C_i \leq 100\,000\,000\) and \(S \times (N-1) \leq C_i\).

题目大意

给定一个数组大小为\(N\)，将进行\(N\)轮操作。第\(i\)轮操作中，除第\(i\)位的数，每个其他数将给第\(i\)位的数 \(S\) 这个值。问在所有轮次的操作当中，最大的 数组中的最小值 是多少？

思路

1.考虑使用小根堆寻找最小值；

2.关键问题在于，每次从堆顶取出的值，要确保为真实值；

3.考虑对于前\(i\)轮，如果堆顶取出的数的位置\(\leq i\)，说明它已经被加过一次；

4.先假设每个数（包括第\(i\)个数本身）在第\(i\)轮都会给第\(i\)个数 \(S\) 这个数，则对于每个被加过的数，都会加上\(N \times S\)这个值；

5.随后，在取出一个真实值之前，前面的每个数应该加上\(N \times S\)这个值的都应该被更新；

6.最终，找到真实值后，其实 其也不是真实值，因为其没有减过数，而假设4.后，可以很方便地认为，这个数在前面每轮都会减 \(S\) 这个值 （在自己的轮次，自减 \(S\) 和自加 \(S\) 相互抵消，刚好满足确保其为真实值），所以要与答案作比较的，即为当前值减$ T \times S\(（\)T$为已经进行的轮次）；

7.在实际代码中，减完的值并没有被更新到小根堆中，因为我们已经让每个数在每轮都会减少$ T \times S$，即一个相同的值，则每个数都减去一个相同的值，对所有数的大小排序并不会产生影响。

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
struct node{
	int x,num;
};
bool operator <(node a,node b){
	return a.x>b.x;
}
priority_queue<node>q;
int n,s,ans;
bool f[100005];
signed main(){
	scanf("%lld %lld",&n,&s);
	for(int x,i=1;i<=n;++i){
		scanf("%lld",&x);
		q.push(node{x,i});
	}
	for(int T=1;T<=n;++T){
		while(q.top().num<=T&&!f[q.top().num]){
			int x=q.top().x+n*s,num=q.top().num;
			q.pop();
			q.push(node{x,num});
			f[num]=1;
		}
		ans=max(ans,q.top().x-T*s);
	}
	printf("%lld",ans);
	return 0;
}

---

C-Statues

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

To escape the loneliness of working remotely everyday, Erika decided to try on a new hobby: sculpture. She already has a large collection of statues and the municipality has allowed her to show her art outside.

Erika wants her statues to be well visible and thus each statue needs to be placed under a distinct street light. Further, the arrangement should be aesthetic which means that the statues should be placed by increasing size with the smallest statues near the beginning of the street and the biggest ones near the end.

Erika placed her statues but she forgot to place them in increasing size and now she has to reposition them in accordance to both of her desires.

The street has \(N\) evenly spaced street lights numbered from \(1\) at the beginning of the street to \(N\) at the end of the street. You estimate the time required to move a statue of size s from the street light \(i\) to the light \(j\) as taking Erika \(s × |i − j|\) units of time. You ask yourself, how much time does it take to reposition all statues knowing that she will use the fastest way possible? Note that she may put statues under street lights that do not have statues at the moment.

输入描述

The first line of the input contains two space-separated integers: \(N\) the number of street lights and \(K\) the number of statues. The \(K\) following lines each contains two space-separated integers, the \(i + 1\)-th line containing the integers \(P_i\) and \(S_i\) describing the \(i\)-th statue. \(P_i\) gives the number of the street light under which the statue is and \(S_i\) gives its size.

输出描述

The output should contain a single line containing a single integer: the minimum amount of time needed to move statues such that each statue is under a different street light and such that the size of statues grows with the street light numbers under which they are.

示例1

输入

3 3
1 3
2 2
3 1

输出

8

说明

Because there are as many street lights as there are statues we need to position the statue of size \(1\) at street light \(1\) (which takes \(1×∣3−1∣=2\) units of times), leave the statue of size \(2\) at street light \(2\), and move the statue of size \(3\) to the street light \(3\)(which takes \(3×∣1−3∣=6\) units of times). In total this takes \(8\) units of time.

示例2

输入

4 3
2 2
3 2
4 1

输出

3

说明

The fastest way of fixing the ordering of statues is to move the statue of size 1 to the street light 1 for a total time of \(1\times|4-1|=3\).

备注

\(1≤K≤N≤5000\)
for all \(1 \leq i\leq K\),\(1\leq S_{i}\leq 1\,000\,000\),\(1\leq P_i \leq N\)

题目大意

给\(N\)个路灯和\(K\)座雕塑。开始时，第\(P_i\)个路灯下有大小为\(S_i\)大小的雕塑。搬运一座雕塑的花费为 \(S \times | i - j |\)（\(S\)为雕塑的大小，\(i,j\)分别为 雕塑所在的路灯坐标 和 目标的路灯坐标）。求最小的花费，使雕塑以 路灯坐标 看，大小为为递增顺序（有些路灯下，可以没有雕塑）。

思路

思路来自大吉大利，晚上吃 mian();的代码

1.因为雕塑本身的大小和路灯的位置都会产生贡献，贪心并不好实现，考虑到\(1≤K≤N≤5000\)，思考使用DP解决；

2.设\(f[x]\)为将 第\(x\)大的雕塑 排好位置后的最小答案

因为我的队友告诉我，mac好像不能开f[5000][5000]的数组；

而且，根据数据，有相同大小的雕像所以对雕塑按大小排序时需要注意一下。

3.考虑状态转移方程，发现这其实是一个背包问题，有

\[f[x]=min(f[x],f[x-1]+S_x*|P_x-i|) \]

此处有一个显然的限制，即为一定为先外层循环一遍路灯坐标，而如果\(i \leq k\)，则第\(i+1\)大的雕塑一定不能放在前\(i\)个路灯的位置上；

即第\(i\)个路灯 放置 第\([1,min(i,k)]\)大的雕塑 后的最小花费；

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    int p,s;
}a[5005];
bool cmp(node x,node y){ 
	if(x.s==y.s) return x.p<y.p;
	return x.s<y.s; 
}
long long f[5005];
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;++i) scanf("%d %d",&a[i].p,&a[i].s);
    sort(a+1,a+1+k,cmp);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;++i)
        for(int j=min(i,k);j>=1;--j)
            f[j]=min(f[j],f[j-1]+1ll*a[j].s*abs(i-a[j].p));
    printf("%lld",f[k]);
    return 0;
}