Codeforces 371E Subway Innovation【思维+前缀和】

admin管理员组

文章数量:1619183

E. Subway Innovation time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter!

The President of Berland was forced to leave only k of the currently existing n subway stations.

The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the Ox axis, the i-th station is at point with coordinate x_i. In such case the distance between stations i and j is calculated by a simple formula |x_i - xj|.

Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such k stations that minimize the average commute time in the subway!

Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is ) and divided by the speed of the train.

Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such k stations that the average commute time in the subway is minimized.

Input

The first line of the input contains integer n (3 ≤ n ≤ 3·10⁵) — the number of the stations before the innovation. The second line contains the coordinates of the stations x_{1, x2, ..., xn} ( - 10^{8 ≤ x_{i ≤ 108}}). The third line contains integer k (2 ≤ k ≤ n - 1) — the number of stations after the innovation.

The station coordinates are distinct and not necessarily sorted.

Output

Print a sequence of k distinct integers t_{1, t2, ..., tk} (1 ≤ t_j ≤ n) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through n in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose k stations. If there are multiple such ways, you are allowed to print any of them.

Examples Input

3
1 100 101
2

Output

2 3 

Note

In the sample testcase the optimal answer is to destroy the first station (with x = 1). The average commute time will be equal to 1 in this way.

题目大意：

给你N个坐标，然后让你选出k个点，使得这k个点中任意取出两点的值：|Ai-Aj|的和最小。

问这个几个坐标的编号。

思路：

不难想到，我们要选的这K个点一定是连续的K个点。

那么我们只要考虑怎样能够在时间复杂度内统计每个点作为起点的价值总和即可。

1、首先我们将所有坐标从小到大排序。

然后我们可以O（k）求出第一段长度为K的子序列的总价值和：

①我们要维护一个数组sum【i】，表示前i个坐标的坐标位子和。

②那么第一段长度为K的子序列的总价值和为：

（i-1）*a【i】-sum【i-1】（2<=i<=k）

2、如果我们暴力枚举起点然后O（k）去求区间总价值和的话，时间复杂度是O（nk）的，显然会超时。

那么我们考虑，对于第一段长度为K的子序列的和的总价值，和第二段长度为k的子序列的和的总价值之间有什么关系?

很显然，蓝色的线是减少的，橙黄色的线是增加的。

这里一条线的意义表示为右边的那个点减去左边那个点的值。

那么我们有前缀和，那么O（1）能够更新下一个区间的总价值和。

细节参考代码

整体思路就是这样，细节参考代码不是很难。

注意数据范围。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll __int64
struct node
{
    ll val,pos;
}a[350000];
ll sum[350000];
int cmp(node a,node b)
{
    return a.val<b.val;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%I64d",&a[i].val),a[i].pos=i;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(i==1)sum[i]=a[i].val;
            else
            sum[i]=sum[i-1]+a[i].val;
        }
        ll maxn=-1000000000000000000;
        ll ans=-1;
        ll k;
        scanf("%I64d",&k);
        ll pre=0;
        for(int i=2;i<=k;i++)
        {
            pre+=(i-1)*a[i].val-sum[i-1];
        }
        maxn=max(maxn,pre);
        ans=1;
        for(ll i=3;i<=n;i++)
        {
            if(i-1+k-1<=n)
            {
                pre+=(k-1)*a[i-2].val-(sum[i-2+k-1]-sum[i-2]);
                pre+=(k-1)*a[i-1+k-1].val-(sum[i-1+k-1-1]-sum[i-2]);
                if(pre<maxn)
                {
                    maxn=pre;
                    ans=i-1;
                }
            }
            else break;
        }
        for(ll i=1;i<=k;i++)
        {
            printf("%I64d ",a[ans+i-1].pos);
        }
        printf("\n");
    }
}

本文标签： 前缀思维codeforcesinnovationSubway