L - 01 Gym - 101078L——数学+double精度

超、凢脫俗 2022-06-10 20:10 111阅读 0赞

Think:  
1知识点：数学+double精度  
2题意：给定1个长度不超过4000的01字符串，通过交换两个字符的位置，使得最终状态第一部分全部为0第二部分全部为1，每交换两个字符的位置，损失sqrt(j-i)，i，j为交换的字符所在位置的下标，询问到达最终状态最少损失和  
3方法：由数学a + b >= 2sqrt(a\*b)可推测得到当a, b接近时取得的值逐渐增大，因此最小损失和即使得所加的每一个字符的损失尽量不接近

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <cmath>
    
    using namespace std;
    
    char st[4014];
    
    int main(){
        int num0, i;
        double sum;
        while(~scanf("%s", st)){
            int len = strlen(st);
            num0 = 0;
            for(i = 0; i < len; i++){
                if(st[i] == '0')
                    num0++;
            }
            queue <int> qa, qb;
            for(i = 0; i < num0; i++){
                if(st[i] == '1')
                    qa.push(i);
            }
            for(i = len-1; i >= num0; i--){
                if(st[i] == '0')
                    qb.push(i);
            }
            sum = 0;
            while(!qa.empty() && !qb.empty()){
                int t1 = qa.front();
                qa.pop();
                int t2 = qb.front();
                qb.pop();
                sum += sqrt(t2-t1);
            }
            printf("%.12lf\n", sum);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/175262#problem/L

发表评论取消回复

表情：

评论列表（有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

相关 NRF24L01驱动程序

NRF24L01驱动模块文件：NRF24L01.c

￡神魔★判官ぃ/ 2022年09月26日 04:54/ 0 赞/ 21 阅读

相关 nRF24L01随笔

1.单片机控制只需关注6个nRF的控制和数据信号： CSN：片选，低电平工作 CE：模式控制 SCK：时钟线 MOSI： MISO： IRQ：中断信号 2.

左手的ㄟ右手/ 2022年09月26日 02:58/ 0 赞/ 166 阅读

相关 I - Keylogger Gym - 101078I——模拟队列+栈

Think: 1知识点：模拟队列+栈 2题意分析：字母输入移动，分别用队列记录输入光标之前内容，用栈记录光标之后可能存在的内容 3其余思路：链表模拟插入结点删除结点

小鱼儿/ 2022年06月11日 06:58/ 0 赞/ 144 阅读

相关 D - Collatz Gym - 101078D——数学

Think: 1知识点：数学 2题意：输入n, 给定1~n的结点，偶数结点m与m/2结点有绳子连接，奇数结点m与结点3\m+1有绳子连接，询问要剪断n+1之后的绳子与1

àì夳堔傛蜴生んèń/ 2022年06月10日 20:20/ 0 赞/ 120 阅读

相关 L - 01 Gym - 101078L——数学+double精度

Think: 1知识点：数学+double精度 2题意：给定1个长度不超过4000的01字符串，通过交换两个字符的位置，使得最终状态第一部分全部为0第二部分全部为1，每

超、凢脫俗/ 2022年06月10日 20:10/ 0 赞/ 112 阅读

相关 Gym - 101086L Chance 解答

Input The first line of input contains an integer T (1 ≤ T ≤ 105), the numb

浅浅的花香味﹌/ 2022年06月10日 11:18/ 0 赞/ 101 阅读

相关 nRF24L01无线介绍

![引脚功能][aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwODA3MTcwODM5NTUz] > CE：RX或TX模式选择 > CS

谁借莪１个温暖的怀抱￠/ 2022年06月10日 01:41/ 0 赞/ 194 阅读

相关 l0-Norm, l1-Norm, l2-Norm, … , l-infinity Norm

原文链接：[http://blog.csdn.net/u011650143/article/details/54695180][http_blog.csdn.net_u0116

Love The Way You Lie/ 2022年06月06日 11:44/ 0 赞/ 235 阅读

相关 Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…

> 题目描述 Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1

Bertha 。/ 2022年05月26日 04:25/ 0 赞/ 224 阅读

相关 Arduino Wireless Communication – NRF24L01 Tutorial(arduino无线通信---NRF24L01教程）

arduino下nrf24l01库文件及相关说明库的说明文档 [https://tmrh20.github.io/RF24/][https_tmrh20.gith

傷城~/ 2021年09月29日 17:28/ 0 赞/ 451 阅读