題意
https://vjudge.net/problem/CodeForces-1250B
每個人屬于隊伍ai，汽車一次至多載兩只隊伍（全員），費用為車的容量*載人次數，問最少花費，
思路
k（隊伍數）只有8000，從這個條件入手這題，先對每個隊伍按人數從小到大排序，那么a[k]就是車的最小容量，于是我們可以列舉車的容量i從a[k]開始，用l=1和r=k從兩端遍歷陣列a，如果a[l]+a[r]<=i，那么l++,r--；否則讓人數大的隊伍先上，即r--，但是如果設車的容量為a[k]+a[k-1]，那么會因為很惡心的資料TLE，所以要優化列舉的容量，我們貪心的分配隊伍上車，一般都會讓人數最多的人數最少的一起上，即a[1]+a[k]，a[2]+a[k-1]，……只要在這些取最大值就是車容量的上限了，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=5e5+5;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll a[N];
int main()
{
std::ios::sync_with_stdio(false);
ll n,k;
cin>>n>>k;
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
a[x]++;
}
if(k==1)
{
cout<<a[1]<<endl;
return 0;
}
ll mx=0;
for(int i=1;i<=k;i++)
{
mx=max(mx,a[i]+a[k-i+1]);
}
sort(a+1,a+1+k);
ll res=1e16;
for(ll i=a[k]; i<=mx; i++)
{
ll l=1,r=k,cnt=0;
while(l<r)
{
cnt++;
if(a[l]+a[r]<=i)
l++,r--;
else
r--;
}
if(l==r)
cnt++;
res=min(res,i*cnt);
}
cout<<res<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127164.html
標籤：其他