WHU 1470 Join in tasks 水题
2024-08-31 17:33:33
http://acm.whu.edu.cn/land/problem/detail?problem_id=1470
大概是给你一个队列,每次移动队头的数到队尾并减1,如果本身这个数为1就删去. 然后ans += 这个数 * (队列长度-1),求最小的ans
只要最小的元素最先删除就能保证结果最小
解法:
先对原数列排序 然后模拟原操作 ...但是t[i] 太大 .显然不能一个个的模拟...其实稍微推一下就能得出 每次到达能删除元素的时候 整个队列循环了t[i]-1次...
我们维护一下后缀和suffix...就能得到这个公式:
前面等差数列,后面等差数列O(1)就能求出 总共n个数,总共O(n)
Notice : 等差数列里面/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 = ()/+;
int main()
{
int T;
scanf("%d",&T);
int cas = ;
for(int cas = ; cas <= T; cas++){
suf = ;
int n,num;
scanf("%d",&n);
num = n-;
for(int i = ; i < n ; i++)
scanf("%lld",&a[i]);
sort(a,a+n);
for(int i = ; i < n ; i++){
suf += a[i];
}
LL res = ;
LL ct = ;
for(int i = ; i < n- ; i++){
a[i] = a[i] - ct;
res = (res + ((a[i]+)%MOD*a[i]%MOD*r2%MOD*num%MOD))%MOD;
int cnt = a[i] - ;
if(cnt > ){
LL sum = (suf + (suf - (cnt-) * num)) % MOD * cnt % MOD * r2 % MOD;
res = (res + (sum*num)%MOD) % MOD;
}
suf -= (num * cnt);
suf = suf - ((a[i+]-ct) - cnt);
num--;
ct += cnt;
}
printf("Case %d: ",cas);
printf("%lld\n",res);
}
return ;
}
最新文章
- 三周,用长轮询实现Chat并迁移到Azure测试
- zepto-selector.js简单分析
- WdatePicker组件不显示
- SPI总线的特点、工作方式及常见错误解答
- Erwin 生成 mysql 带注释(comment )的脚本
- jdk1.8 J.U.C之FutureTask实现机制分析
- 操作properties文件,注意抹掉最前面的";file:";
- jquery-ui 之Sortable详解
- Firebug控制台详解
- 008实现一个算法从一个单链表中返回倒数第n个元素(keep it up)
- 【ALB学习笔记】基于事件触发方式的串行通信接口数据接收案例
- eclipse中添加Java代码注释模板
- Android实现横屏以及全屏的小技巧
- 北京大学Cousera学习笔记--8-计算导论与C语言基础--C的运算部分
- chrome的console功能
- IdentityServer4 中文文档 -14- (快速入门)使用 ASP.NET Core Identity
- IndexDB 操作util
- HTML基础之HTML标签
- 20145109竺文君、20145106石晟荣 java实验三
- Window 编码 UTF-8 BOM 说明