题解 | #阿宁吃粽子#

阿宁吃粽子

• 题目描述

• 题目分析（思路）：

• 运行代码:

  • 方法一：运用“队列”的方式（最容易理解的idea）
  • 方法二：运用“Vector容器分组”计数

题目描述

阿宁的公司给阿宁发了各种口味的粽子。 一共有 n 条粽子，每条粽子有个美味值 ai,阿宁想立即吃下全部。吃下第 k 条粽子时，该粽子的美味值是 x，阿宁获得 2^(k mod10)*x 的愉悦值。（k 从 1 开始）阿宁想安排一下吃粽子的顺序，使她获得的愉悦值最大。

题目分析（思路）：

其实这是一道思维题，我就是那种看了大佬的代码都看不懂的萌新，但是有时候，诶~，突然get到了大佬的意思了

1.要使总愉悦值大的话，要明白每个愉悦值取决于2^k*mod10中的k值的最后一位；

2.要先把最小的美味值依次赋值（最后一位）顺序为0~9；

eg：假设n=19，第一个最小的美味值应该在第10个吃粽子；

第二个小的美味值，是第一个吃；（如果n>20,那么第二个小的美味值是在第二十个吃粽子，以此类推）

第三个是第11个吃，第四个是第2个吃…… **

运行代码:

方法一：运用“队列”的方式（最容易理解的idea）

#include <bits/stdc++.h>
using namespace std;
const int mx=6e5+100;
int n,a[mx],c[mx];
queue<int>q;
int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0; i<n; i++)
    {
        q.push(a[i]);
        //cout<<a[i]<<endl;
    }//只是为了让美味值从小到大进入队列；所以我这里借用了数组先存储排序；
    for(int j=0; j<=9; j++)
    {
        int t=0,temp;
        while((t+j)<=n&&!q.empty())
        {
            if((t+j)!=0)
            {
                temp=q.front();
                c[t+j]=temp;
                q.pop();
            }

            //cout<<"c["<<t+j<<"]:"<<temp<<endl;

            t+=10;
        }
    }//对应每个吃粽子的顺序，找到了就把美味值弹出去；队列的第一个永远是最小的；
    for(int i=1; i<=n; i++)
    {
        if(i==1)
            cout<<c[i];
        else
            cout<<" "<<c[i];
    }
    cout<<endl;//对应题目的格式输出


}

方法二：运用“Vector容器分组”计数

在输出这块还可以用递归去写，但是会更麻烦一点

#include<bits/stdc++.h>
using namespace std;
int n,k,k1,s=1,a[300005];
vector<int>e[12];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    k=n/10;//组数，满十为一组
    k1=n%10;//多出几个
  
    for(int i=0; i<=9; i++)//落实分组的内容，利用数组容器，e[i]的i是指数；有点涩，带样例二进去走一遍会容易理解
    {
        for(int j=s; i<=k1&&i>=1?j<s+(k+1):j<s+k; j++)//
            e[i].push_back(a[j]);
        if(i<=k1&&i>=1)
            s+=(k+1);
        else
            s+=k;
    }
    for(int i=0; i<e[1].size(); i++)//无论n为多大，余数为1的一定是最多的
    {
        for(int j=1; j<=10&&e[j%10].size()>=i+1; j++)//从1~9在0的顺序输出
            cout<<e[j%10][i]<<' ';
    }
}