首页 > 其他分享 >洛谷 P1223 排队接水

洛谷 P1223 排队接水

时间:2023-01-03 00:22:27浏览次数:64  
标签:std 洛谷 int 排队 等待时间 P1223 const

题目传送门:https://www.luogu.com.cn/problem/P1223
题目:
Description:
有 nn 个人在一个水龙头前排队接水,假如每个人接水的时间为 Ti,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。
Input:
第一行为一个整数n;
第二行n个整数,第i个整数Ti;表示第i个人的等待时间Ti。
Output:
输出文件有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
题解:贪心。首先我们需要知道什么叫做“平均等待时间”?“平均等待时间”意思就是每个人等待的时间加起来然后除以人数n。知道这个之后题目就很简单了,我们只要想着把每个人等待的时间加起来尽量少就行了,那是不是就意味着只要让每个人的前缀和尽可能小不久行了,所以我们只要把数值小的元素放在前面不就实现了嘛,直接sort排序输出即可,用pair记录数值和下标即可。

点击查看代码
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
pii a[1010];
int main(void)
{
    // Zeoy;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i].first;
            a[i].second = i;
        }
        sort(a + 1, a + n + 1);
        double ans = 0.0, sum = 0.0;
        for (int i = 1; i <= n; ++i)
        {
            cout << a[i].second << " ";
            ans += sum;
            sum += 1.0 * a[i].first;
        }
        cout << endl;
        printf("%.2f\n", ans / n);
    }
    return 0;
}

标签:std,洛谷,int,排队,等待时间,P1223,const
From: https://www.cnblogs.com/Zeoy-kkk/p/17020900.html

相关文章

  • 洛谷P1862输油管道问题
    题目传送门二话不说先上代码:#include<bits/stdc++.h>usingnamespacestd;intn;intx,y[10001];intmain(){ scanf("%d",&n); for(inti=1;i<=n;i++){ scanf("%......
  • AcWing1170. 排队布局[USACO05]
    解题思路\(\qquad\)这题也是一个比较裸的差分约束:多了的那个输出\(-2\)的其实就是在差分约束系统中\(1\)号点和\(n\)号点没有约束关系,也就是\(1\)和\(n\)号不连通。由于这......
  • 洛谷 P5721 【入门3】循环结构
    P5723【深基4.例13】质数口袋1.题目描述小A有一个质数口袋,里面可以装各个质数。他从 2 开始,依次判断各个自然数是不是质数,如果是质数就会把这个数字装入口袋。口......
  • 洛谷P4146 序列终结者 题解 splay tree
    题目链接:​​https://www.luogu.com.cn/problem/P4146​​题目大意:支持:区间更新(+x)区间翻转区间查询(最大值)解题思路:几乎和​​AcWing2437.Splay​​这题一模一样。示例程......
  • 洛谷 P5721 【深基4.例6】数字直角三角形
    题目描述给出nn,请输出一个直角边长度是nn的数字直角三角形。所有数字都是22位组成的,如果没有22位则加上前导00。输入格式输入一个正整数nn。输出格式输出如......
  • 洛谷 P2395 BBCode转换Markdown 题解
    洛谷P2395BBCode转换Markdown题解题目传送门:here.一道毒瘤的大模拟,给了你一部分的BBCode和Markdown语法,叫你转换。如下表:BBCodeMarkdown[h1]文字[/h1......
  • AcWing 1359. 洛谷P1457 城堡
    解题思路\(\qquad\)这道题目是需要维护各种连通块信息的,所以这里我们可以也用并查集维护。这题我们如果注意一点细节,也是可以让代码变得很简洁的:\(\qquad\quad1.\)这道......
  • 分布式排队叫号系统源码出售
    我司开发的分布式排队叫号系统,支持政务大厅、银行、工商、税务等应用场景。1、采用C/S和B/S混合架构,后台采用B/S架构,易于维护2、支持WINDOWS、android系统3、兼容多种LED屏......
  • 洛谷P2296 [NOIP2014 提高组] 寻找道路 题解
    题目链接:P2296[NOIP2014提高组]寻找道路-洛谷|计算机科学教育新生态(luogu.com.cn)好了,话不多说上代码:1#include<bits/stdc++.h>2usingnamespacestd;3......
  • 还在打印店排队打印文件?足不出户就能在线自助打印的系统
    如果你需要打印一些文件,那么你会选择怎么样的打印方式呢?相信很多人的第一反应就是去周边打印店打印文件,但是现在路边越来越多的打印店消失不见了,即便是找打一家打印店,在遇......