专栏首页小L的魔法馆第十四届浙江财经大学程序设计竞赛重现赛--A-A Sad Story

第十四届浙江财经大学程序设计竞赛重现赛--A-A Sad Story

链接:https://www.nowcoder.com/acm/contest/89/A 来源:牛客网

  • 1.题目描述 The Great Wall story of Meng Jiangnv’s Bitter Weeping happened during the Qin Dynasty (221BC- 206BC). Meng jiangnv was a beauty in the Qin Dynasty, and she lived happily with her husband. At that time, Emperor Qin Shihuang (the first emperor of Qin) announced to build the Great Wall. And the officials suddenly broke in their happy life and took Meng’s husband away to build the wall. Because of the missing for her husband, she decided to set off to look for her husband. After a long journey, finally she reached the foot of the Great Wall at the present Shanhaiguan Pass. Upon her arrival, a bad news came to her, however, her husband had already died of exhaustion and was buried into the Great Wall! Meng could not help crying. She sat on the ground and cried and cried. Suddenly with a tremendous noise, a 400 kilometer-long (248-mile-long) section of the wall collapsed over her bitter wail. Today, Qin Shihuang gets N stones. The height of the ith stone is Ai. He will use all these stones to rebuild the Great Wall. In order to make the Great Wall more sturdy, the prime minister Li Si proposes a formula to calculate the “weakness” of the reconstructed Great Wall

The Bi is the height of the ith stone in the reconstructed Great Wall, and the K is provided by Li Si. For example, Qin Shihuang gets 5 stones. The height of these stones are [5,3,2,4,1], and the K is 2. There are 120 different ways to rebuild the Great Wall. The following figures show the two solutions:

The weakness of left figure and right figure are 4 and 11, respectively. Now, Li Si wants to know the minimum value of “weakness”. Li Si is too old to calculate the answer quickly, so he asks you for help. 输入描述: The first line contains an integer T, where T is the number of test cases. T test cases follow. For each test case, the first line contains two integers N and K, where N is the number of stones and K is a variable which provided by Li Si. The second line contains N integers A1, A2, … , AN, where Ai is the height of the ith stone that QinShiHuang gets. • 1 ≤ T ≤ 50. • 1 ≤ N ≤ 103. • 1 ≤ K ≤ N. • 1≤ Ai ≤104. 输出描述: For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minimum value of “weakness”. 示例1 输入 2 5 2 1 2 3 4 5 5 3 1 3 2 2 7 输出 Case #1: 4 Case #2: 7 备注: For the first case, one of the best ways is [1,2,3,4,5], weakness = (2−1)+(3−2)+(4−3)+(5−4) = 4. For the second case, one of the best ways is [7,3,2,2,1], weakness = (7−2)+(3−2)+(2−1) = 7.

  • 2.题目分析 关键就是着weakness的计算公式,它计算的是所有a[i+k-1]-a[i]的值,同时a[i+k-1](最大)-a[i](最小),所以做法就是先递增排序,累加所有a[i+k-1]-a[i]的值,输出结果就是答案
  • 3.代码如下
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
char str1[2000], s2[2000];
int dp[105];
int ap[105], bp[105];
const int  MAXN= 1000005;
int a[10005];
int main()
{   
    int T,d=1;
    scanf("%d",&T);
    while(T--)
    {   
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        int res=0;
        for(int i=0;i+k-1<n;i++)
        {
            res+=a[i+k-1]-a[i];
        }         
        printf("Case #%d: %d\n",d++,res);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2007--Scrambled Polygon(计算凸包,点集顺序)

    Scrambled Polygon Time Limit: 1000MS Memory Limit: 30000K Total Submiss...

    Enterprise_
  • B. Train Seats Reservation 2017 ACM-ICPC 亚洲区(南宁赛区)网络赛

    You are given a list of train stations, say from the station 1 to the station 10...

    Enterprise_
  • 2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛- A. Banana

    In the forest, there is a Banana Company that provides bananas from different pl...

    Enterprise_
  • HTTP权威指南_摘录

    以下内容是摘录自《HTTP 权威指南》(HTTP The Definitive Guide),目前没有中文版,可在google中阅读部分章节。有兴趣想购买的可以...

    meteoric
  • Flexbox 练习和总结

    练习地址: http://flexboxfroggy.com/ Welcome to Flexbox Froggy, a game where you help...

    SmileSmith
  • numpy.geomspace

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明...

    于小勇
  • Kotlin 函数编程详解函数Kotlin 开发者社区

    Functions in Kotlin are declared using the fun keyword:

    一个会写诗的程序员
  • Pat 1052 Linked List Sorting (25)

    1052. Linked List Sorting (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000...

    ShenduCC
  • Code Forces 645B Mischievous Mess Makers

    It is a balmy spring afternoon, and Farmer John’s n cows are ruminating about li...

    ShenduCC
  • gcc命令

    在Linux底下搞开发,不可避免的要使用到gcc,gcc选项众多,下面记录下常见的一些选项,网上好多博客也说这个但是很多的都是不对的,我的博客记录参见man g...

    GavinZhou

扫码关注云+社区

领取腾讯云代金券