題目：
思路：
比賽前再睡覺我是狗
這題沒想到優化是在這里
對存入的學校離散化一下（防止MLE）
然后對每個學校的學生得分進行降序排序
再對所有學校的學生人數進行降序排序
統計一下每個學校的得分前綴和
然后關鍵優化時間的思想：
如果存在一個人數非常多的學校，那么別的學校的總人數都很少
雙重回圈統計在每個分塊長度時所有學校的總分
如果有學校的總人數不夠分塊
那么直接跳過，開始下一個長度的分塊計算
所以看似雙重回圈，但時間大大縮短，有很多用不到的都沒統計了
代碼：
#include <algorithm>
#include <unordered_map>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define G 10.0
#define LNF 1e18
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long
#define INF 0x7FFFFFFF
#define Regal exit(0)
#define Chivas int main()
#define pb(x) push_back(x)
#define SP system("pause")
#define ull unsigned long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define IOS ios::sync_with_stdio(false)
#define mm(a, b) memset(a, b, sizeof(a))
#define each_cass(cass) for (cin >> cass; cass; cass--)
#define test(a) cout << "---------" << a << "---------" << '\n'
using namespace std;
bool cmp(vector<ll> a, vector<ll> b){return a.size() > b.size();}
inline void solve()
{
ll n;
cin >> n;
unordered_map<ll, ll> mp;//記錄出現過這個學校編號沒
ll u_cnt = 0;
vector<ll> a;
for (ll i = 0, x; i < n; i++){
scanf("%lld", &x);
if (!mp[x]){
mp[x] = ++u_cnt;//離散化建立編號與離散結果的映射
}
a.push_back(x);
}
vector<ll> uni[u_cnt + 10];
for (ll i = 0, x; i < n; i++){
scanf("%lld", &x);
uni[mp[a[i]]].push_back(x);
}
for (ll i = 1; i <= u_cnt; i++)
sort(uni[i].begin(), uni[i].end(), greater<ll>());
sort(uni + 1, uni + u_cnt + 1, cmp);//從大到小排序可以跳過后面的
vector<vector<ll> > sumfro(u_cnt + 10);//記錄前綴和
for (ll i = 1; i <= u_cnt; i++){
ll len = uni[i].size();
for (ll j = 0; j < len; j++){
if (j == 0)
sumfro[i].push_back(uni[i][j]);
else
sumfro[i].push_back(sumfro[i].back() + uni[i][j]);
}
}
ll sum[n + 10] = {0};
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= u_cnt; j++)
{
if ((uni[j].size()) / i > 0)
sum[i] += sumfro[j][uni[j].size() / i * i - 1];
else//精華：卡我所在，小于i的都不算
break;
}
}
for (int i = 1; i <= n; i++)
printf("%lld ", sum[i]);
printf("\n");
}
Chivas
{
ll cass;
scanf("%lld", &cass);
while (cass--)
{
solve();
}
Regal;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/282129.html
標籤：其他
上一篇：用戶資訊獲取修改