CSA Round #54 $\ $Voting

时间：2023-03-10 00:10:36
CSA Round #54 $\ $Voting

CSA Round #54 \(\ \)Voting

题目大意：

原题网址：戳我戳我！
一次歌唱比赛中,一位歌手刚刚结束表演,评委正在打分。
一共有 \(n\) 位评委,他们每人可以打 \(1\) 分或 \(0\) 分,第 \(i\) 位评委希望歌手的得分为 \(v[i]\)。
评委们有特殊的控分技巧,他们会按一个顺序依次评分,
第一个评分的评委会不管三七二十一打 \(0\) 分。
对于接下来的评委,假设前面 \(a\) 位评委评分总和为\(b\), 评委会认为这位歌手期望得分为 \(\frac{b}{a}n\),
如果这个得分低于他所希望的得分,他会打 \(1\) 分,否则他会打 \(0\) 分。
你希望选手的得分为 \(p\)\((0\leq p\leq n)\),为此你可以调换评委们的评分顺序。
你需要输出一个 \(1～n\) 的排列,第 \(i\) 个位置表示第 \(i\) 个评分的裁判的编号,让选手的得分最接近 \(p\)。
如果有多种,你只需要输出任意一种。

思路解法

假设裁判的期望得分是有序的,那么按编号顺序投票得分最大,按编号顺序倒序投票得分最小。
这个非常的显然。证明之类的略。
然后我们可以发现一个至关重要的结论：

如果评分顺序中相邻两位裁判的期望得分为\(a\)和\(b\),
并且\(a\leq b\),那么交换这两位裁判,答案要么不变要么减少\(1\)。

证明如下 , 一共分四种情况，假设原来：

  • a=0且b=0 ，交换后，a、b的前面状态未变，仍为0，答案不变。
  • a=1且b=0 ，交换后，b为1(比b怂的a在那里都为1)，a的状态未知，答案不变或者减一。
  • a=0且b=1 ，交换后，b为1 且 a为0，b的前面状态未变，a在前面都是0到后面更不可能为1了，答案不变。
  • a=1且b=1 ，交换后，b为1显然，a的状态未知，答案不变或减一。
  • 综上所述，若\(a\leq b\)，交换\(a\)与\(b\)后，答案不变或者减一。

考虑\(1\ 2\ 3\ 4\ 5\ ...\ n\)如何每次交换一个相邻的顺序对变成\(n\ n-1\ ...\ 2\ 1\) 。
其实与冒泡排序差不多：
\(1\ 2\ 3\ 4\) >>> \(1\ 2\ 4\ 3\) >>> \(1\ 4\ 2\ 3\) >>> \(4\ 1\ 2\ 3\) >>> \(4\ 1\ 3\ 2\ \)>>>\(4\ 3\ 1\ 2\)>>>\(4\ 3\ 2\ 1\)
由我们上面得到的结论可知，总分\(score\)是不断递减的。
设最大得分为\(Max\)，最小得分为\(Min\)。
我们可以断定，如果\(p\in [Min,Max]\)，那么一定是可以取到的。
所以我们二分上述交换进行了多少次，然后构造出此时的序列，计算出此时的分数继续处理即可。
如果无解，那么最终答案序列为最大或最小值序列中的一个。

实现代码

注：此题代码实现中，变换顺序与上述相反,为\(n\ ...\ 2\ 1\)变到\(1\ 2\ ... \ n\)。

#include<bits/stdc++.h>
#define RG register
#define IL inline
#define ll long long
#define _ 500005
using namespace std;

ll pre[_] , stp[_] , n , p , f[_] , score;
struct Judger { ll v , id ; } q[_] ;  ll L , R , l , r; bool flag;

IL bool cmp(RG Judger A,RG Judger B){return A.v > B.v;}

IL int GetBlock(RG ll ps){
    l = 0 , r = n-1 ; RG ll res = -1;
    while(l <= r){
        RG ll mid = (l + r) >> 1;
        if(pre[ mid ] <= ps){res = mid; l = mid + 1;}
        else r = mid - 1;
    }return res;
}

IL ll Calc(){
    RG ll res = 0;
    for(RG ll i = 2; i <= n; i ++)
        if(res * n < (i-1) * q[f[i]].v)res ++;
    return res ;
}

IL void Rest(){
    for(RG ll i = 1; i <= n; i ++)f[i] = i;
    score = Calc();
    for(RG ll i = 1; i <= n; i ++)f[i] = n-i+1;
    if(abs(p - score) < abs(p - Calc()))
        for(RG ll i = 1; i <= n; i ++)f[i] = i;
    return;
}

IL void Build(RG ll mid){
    RG ll blk = GetBlock(mid),rest,t;
    for(RG ll i = 1; i <= blk; i ++)f[i] = i;
    rest = mid - pre[blk]; ++ blk;
    t = blk + 1;
    for(RG ll i = n; i >= n-rest+1; i --)f[i] = t ++;
    f[n - rest] = blk;
    for(RG ll i = n-rest-1; i >= blk; i --)f[i] = t ++;
}

int main(){
    cin >> n >> p;
    for(RG ll i = 1; i <= n; i ++)
        cin >> q[i].v  , q[i].id = i;
    sort(q + 1,q + n + 1,cmp);
    for(RG ll i = 1; i <= n; i ++)stp[i] = n - i;
    for(RG ll i = 1; i <= n; i ++)pre[i] = pre[i-1] + stp[i];
    flag = false;
    L = 0; R = n * (n-1) / 2;
    while( L <= R ){
        RG ll mid = (L + R) >> 1;
        Build(mid);
        score = Calc();
        if(score == p){flag = true; break;}
        else if(score < p)R = mid - 1;
        else L = mid + 1;
    }
    if(!flag)Rest();
    for(RG ll i = 1; i <= n; i ++)printf("%lld ",q[f[i]].id);
    return 0;
}

随机推荐

  1. JS原型学习之旅（一）之一图了解原型链关系

    目前正在学JS的原型思想(准确的说是从昨天2018.1.29开始正式接触),琢磨了两天,在chrome的console不停的敲了好多代码测试__proto__和prototype的关系,有了些小收获( ...

  2. python爬虫（2）——编写一个爬虫

    一.URL的编码与解码 在python2中包含的urllib和urllib2,都是接受URL请求相关的模块.但是在python3中,却没有urllib2.实际上urllib2的功能在python3中可 ...

  3. 菜鸟的it之路-起航

    之前在知乎上看见怎么学习数据结构下一位答主的回答,他引用了N.Wirth(沃斯)的话:程序=数据结构+算法.(哈,菜鸟无法验证这句话的正确性有多大)但毫无疑问的是,数据结构应当是一名菜鸟程序狗要重点学 ...

  4. main函数的实现解析

    main函数的传参的实现,其实也是一个解析字符串的过程:将每个word后一个空格改为“/0”,将单词提取出来. 就是这么简单. 废话不多说,直接上代码: #include<stdio.h> ...

  5. 自动创建字符设备，不需mknod

    自动创建设备文件 1.自动创建设备文件的流程 字符设备驱动模块 -->创建一个设备驱动class--->创建属于class的device--->调用mdev工具(自动完成)--&gt ...

  6. shiro权限控制的简单实现

    权限控制常用的有shiro.spring security,两者相比较,各有优缺点,此篇文章以shiro为例,实现系统的权限控制. 一.数据库的设计 简单的五张表,用户.角色.权限及关联表: CREA ...

  7. sql server两个时间段内，求出周末的量

    公司有个表记录了出差(加班)的初始时间和截止时间,现在要计算出加班时间,之前的设计并没有考虑到这部分,因此本人通过sql重新计算周末数 表formmain starttime endtime 使用游标 ...

  8. Java经典编程题50道之四十九

    计算某字符串中子串出现的次数. public class Example49 {    public static void main(String[] args) {        String s ...

  9. JavaScript面向对象学习笔记

    JavaScript 常被描述为一种基于原型的语言 (prototype-based language)--每个对象拥有一个原型对象,对象以其原型为模板.从原型继承方法和属性.原型对象也可能拥有原型, ...

  10. 重磅发布：《阿里巴巴Android开发手册(规约)》

    1.前言 阿里巴巴于近日为广大程序员再送上重磅开春好礼:<阿里巴巴Android开发手册(规约)>.该开发规范在阿里内部经过了长期的修缮,现已总结成册,向所有移动开发者.技术爱好者开放,希 ...

相关文章