链接

题意：

某公司的员工们要庆祝今天的第$256$天！该公司有$n$名员工和$k$个团队，每个员工仅属于$1$个团队，每个团队至少有$1$名员工。团队编号从$1$到$k$。现在给出$n$个数字：$t_1,t_2,……t_n$表示第$i$个员工属于第$t_i$ 个团队。该公司雇佣了一辆班车，这辆班车将会往返多次承载员工去参加宴会，每一次可以承载$1$个团队或者$2$个团队，且每一个团队不能分离，必须在同一次车上。这辆车可以承载$s$个员工，$s$可以为任意值，假设通过$r$次运输，所有的员工都到达宴会目的地了，该公司需要支付$sr$元(只有$1$辆班车)。现在要你计算$rs$的最小值。

$(n<=2e5,k<=8000)$

分析：

首先我们看两个属性 车的最大容量和车的数量,我们看他们的范围，因为我们想枚举这两个属性中的其中一个，来求答案。

• 车数量：首先看数据范围为 $[\frac{k+1}{2},k]$ 左端点是都一个车放两组，右端点是一个车放一组。两个极端情况，然后再内层循环去取者k个数，复杂度还是$O(n^2)$抱着侥幸心理交了一下，T44.没错还是太大了 。毕竟是8000*8000.

  //枚举方式 ： 车数量：
  void check(int i)
  {
       
    bool flag = 0;
    ll sum = 0;
    priority_queue<ll, vector<ll>, greater<ll> > mx;
    for(int j = k; j >= 1; j--)
    {
       
        if(flag == 0)
        {
       
            mx.push(b[j]);
        }
        else
        {
       
            ll top = mx.top();
            mx.pop();
            sum = max(top + b[j], sum);
        }
        if(mx.size() == i) flag = 1;
    }
    while(!mx.empty())
    {
       
        sum = max(sum, mx.top());
        mx.pop();
    }
    ans = min(sum * i, ans);
  }
  

• 然后看按照车的最大容量数据范围是， 最小就是最大的那组 $b[k]$(排序后最后一个).最大为，两两结对最后两个结对也就是：$b[k]+b[k-1]$，这样再在内层循环放k个物品(我们可以用尺取去放)，这样复杂度外层的 其实是 平均下来就是[n/k]但是不准，但是可以过。然后内层枚举的是k。

虽然枚举车的最大容量可以过但是不知道怎么就出问题了，尺取代码中的$l,r$设成ll就T，改成int就能过，有巨巨懂的话可以解释下吗？万分感谢。

///苟利国家生死以，岂因祸福避趋之。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 8000 + 7;
ll n, k;
ll b[maxn];
ll ans=1e18;

//枚举方式： 车的最大容量
void check(ll x)
{
   
    ll tmp = 0;
    int l = 1, r = k;
    while(l <= r) ///尺取
    {
   
        tmp++;
        if(l == r) break;
        if(b[l] + b[r] <= x) l++, r--;
        else r--;
    }
    ans = min(tmp * x, ans);
}

int main()
{
   
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    {
   
        ll x;
        scanf("%lld",&x);
        b[x]++;
    }
    sort(b + 1, b + 1 + k);
    for(ll i = b[k]; i <= b[k] + b[k - 1]; i++)
    {
   
        check(i);
    }
    cout<<ans;
    return 0;
}

链接

题意:

定义一个数的“Reflecion number”，是用9减去它的每一个数位后,再去掉前导0而形成的数，如192的“Reflecion number”是807（9-1=8，9-9=0，9-2=7）。

再定义一个数的“Weight”，它等于这个数自身乘以这个数的“Reflecion number”。

输入l和r${1<=l<=r<=10^9}$，输出l到r的数中"Weight"的最大值。

分析：

首先我们先看他们乘积发现他们的关系，
一个数x 的Re number 数是什么？ 手模一个数 897 ,他的Re NUM为 (9-8)(9-9)(9-7)发现是102他与原数的关系是897+102=999，那么我们就可以直接通过求出其位数然后这么多9减去原数就是原数的Re number，然后我们就可以直接求出结果。

然后我们看看其具有的性质，我们发现答案不是最小的那个数，就是最大的那个数，要不就是5000...中间这个数，然后我们发现我们要先整出最优的一位数。后面就叠加。

///苟利国家生死以，岂因祸福避趋之。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
const double pi = 3.14159265358979;


ll l,r;
ll g(ll x)///求函数
{
   
    ll t = 1;
    while (t <= x) t*=10;
    return (t-1-x)*x;
}

int main()
{
      
    cin >> l >> r;
    ll res = max(g(l),g(r));    
    ll t = 5;
    for(int i=0;i<=9;i++)
    {
   
        if (l <= t && t <= r)
            res = max(res,g(t));
        t*=10;
    }
    cout << res << endl;
    return 0;
}