http://acm.whu.edu.cn/land/problem/detail?problem_id=1470

大概是給你一個隊列,每次移動隊頭的數(shù)到隊尾并減1,如果本身這個數(shù)為1就刪去.?然后ans?+=?這個數(shù)?*?(隊列長度-1),求最小的ans

只要最小的元素最先刪除就能保證結果最小

解法:?

先對原數(shù)列排序?然后模擬原操作?...但是t[i]?太大?.顯然不能一個個的模擬...其實稍微推一下就能得出?每次到達能刪除元素的時候?整個隊列循環(huán)了t[i]-1次...

我們維護一下后綴和suffix...就能得到這個公式:?

前面等差數(shù)列,后面等差數(shù)列O(1)就能求出?總共n個數(shù),總共O(n)

Notice?:?等差數(shù)列里面/2不能隨意取模,我們要對2求1e9+7的逆元再取模

過程舉例: 2?3?4?5?6

第一輪:? 2?3?4?5?6? 　　to? 1?2?3?4?5

第二輪: 2?3?4?5　　　　to 1?2?3?4

第三輪: ?2?3?4 　　　　?to 1?2?3

第四輪: 2?3 　　　　　 to 2

第五輪: 2 (結果懶得寫了...自己可以拍一下)

?

/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std;#define EPS 1e-8 #define MAXN 100005 #define MOD ((int)1e9+7) #define PI acos(-1.0) #define DINF (1e10) #define LINF ((1LL)<<50) #define INF (0x3f3f3f3f) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define line cout<<"--------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #define FOUT freopen("out.txt","w",stdout) #pragma comment (linker,"/STACK:102400000,102400000")typedef long long LL; typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; } // LL lcm(LL a,LL b){ return a*b/gcd(a,b); }/********************* F ************************/ LL suf; LL a[MAXN]; LL r2 = (1000000007)/2+1; int main() {int T;scanf("%d",&T);int cas = 1;for(int cas = 1; cas <= T; cas++){suf = 0;int n,num;scanf("%d",&n);num = n-1;for(int i = 0 ; i < n ; i++)scanf("%lld",&a[i]);sort(a,a+n);for(int i = 1 ; i < n ; i++){suf += a[i];}LL res = 0;LL ct = 0;for(int i = 0 ; i < n-1 ; i++){a[i] = a[i] - ct;res = (res + ((a[i]+1)%MOD*a[i]%MOD*r2%MOD*num%MOD))%MOD;int cnt = a[i] - 1;if(cnt > 0){LL sum = (suf + (suf - (cnt-1) * num)) % MOD * cnt % MOD * r2 % MOD;res = (res + (sum*num)%MOD) % MOD;}suf -= (num * cnt);suf = suf - ((a[i+1]-ct) - cnt);num--;ct += cnt;}printf("Case %d: ",cas);printf("%lld\n",res);}return 0; }

?

?

?

?

轉載于:https://www.cnblogs.com/Felix-F/p/3279689.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的WHU 1470 Join in tasks 水题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。