Problem 1 世界上最可愛的珂朵莉###

時間限制：C/C++ 1秒，空間限制：C/C++ 65536K

題目描述
我永遠(yuǎn)喜歡珂朵莉~！
有兩個長為n的序列a[i]與b[i]
你可以把任意不多于x個a序列中的數(shù)變成y
你可以把所有序列b中的數(shù)減去一個非負(fù)數(shù)t
你可以把a(bǔ)序列和b序列分別任意打亂
要求對于1 <= i <= n滿足a[i] >= b[i]
求t的最小值

輸入描述:
第一行三個數(shù)n,x,y
之后一行n個數(shù)表示a序列
之后一行n個數(shù)表示b序列

輸出描述
一行一個非負(fù)數(shù)表示答案
輸入示例1
輸入
10 0 233333
227849 218610 5732 128584 21857 183426 199367 211615 91725 110029
8064826 14174520 10263202 9863592 592727 7376631 5733314 1062933 12458325 15046167
輸出
14818318

數(shù)據(jù)范圍
對于100%的數(shù)據(jù)，0 <= n <= 200000 , 0 <= x,y <= 2000000000，0<=a[i],b[i]<=2000000000

分析：
如果沒有1操作將a序列中的數(shù)變成y，則改題只需要將a和b分別排序，然后找出對應(yīng)位置的最大差值即可。
現(xiàn)在有操作1，則先將a序列排好序，然后從小到大將a序列中的值與y依次比較，如果小于y，就更換。再重新對變換后的a序列排序，將a序列和b序列依次比較，尋找相應(yīng)位置上最大的差值即為所有答案！

#include<bits/stdc++.h>
using namespace std;

int A[200010], B[200010];
 
int main()
{
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    for(int i = 0; i < n; i++) 
		scanf("%d", &A[i]);
    for(int i = 0; i < n; i++) 
		scanf("%d", &B[i]);
    sort(A, A+n);
    sort(B, B+n);
    for(int i = 0; i < n; i++)
    {
        if(x!=0 && A[i] < y) 
		{
			A[i] = y, x--;
		}
        if(x <= 0 || A[i] > y) break;
    }
    sort(A, A+n);
    int Ans = 0;
    for(int i = 0; i < n; i++) 
		Ans = max(Ans, B[i]-A[i]);
    printf("%d\n", Ans);
    return 0;
}

電池的壽命###

總時間限制: 1000ms 內(nèi)存限制: 65536kB

問題描述####

小S新買了一個掌上游戲機(jī)，這個游戲機(jī)由兩節(jié)5號電池供電。為了保證能夠長時間玩游戲，他買了很多5號電池，這些電池的生產(chǎn)商不同，質(zhì)量也有差異，因而使用壽命也有所不同，有的能使用5個小時，有的可能就只能使用3個小時。顯然如果他只有兩個電池一個能用5小時一個能用3小時，那么他只能玩3個小時的游戲，有一個電池剩下的電量無法使用，但是如果他有更多的電池，就可以更加充分地利用它們，比如他有三個電池分別能用3、3、5小時，他可以先使用兩節(jié)能用3個小時的電池，使用半個小時后再把其中一個換成能使用5個小時的電池，兩個半小時后再把剩下的一節(jié)電池?fù)Q成剛才換下的電池（那個電池還能用2.5個小時），這樣總共就可以使用5.5個小時，沒有一點浪費(fèi)。
現(xiàn)在已知電池的數(shù)量和電池能夠使用的時間，請你找一種方案使得使用時間盡可能的長。

輸入格式####

輸入包含多組數(shù)據(jù)。
輸入第一行，一個整數(shù)T，表示數(shù)據(jù)的組數(shù)。
接下來每組數(shù)據(jù)包括兩行，第一行是一個整數(shù)N (2 ≤ N ≤ 1000)，表示電池的數(shù)目，第二行是N個正整數(shù)表示電池能使用的時間。

輸出格式####

對每組數(shù)據(jù)輸出一行，表示電池能使用的時間，保留到小數(shù)點后1位。
樣例輸入
2
2
3 5
3
3 3 5
樣例輸出
3.0
5.5

問題分析####

初看之下，本題感覺沒有什么很好的思路，但應(yīng)該有貪心的辦法。
由于每枚電池的使用時間不同，而我們又要減少浪費(fèi)才能使所有電池加起來用得最久，不難發(fā)現(xiàn)：如果我們把使用時間最長的電池比喻成第一戰(zhàn)隊，其他電池比喻成第二戰(zhàn)隊，使用時間就是戰(zhàn)斗力，
每次從拿電池使用時間最長的和另外戰(zhàn)隊里電池使用時間最長的相互戰(zhàn)斗消耗1個戰(zhàn)斗力；并且在每次戰(zhàn)斗后，重新調(diào)整戰(zhàn)隊的分配情況(最大電池容量可能發(fā)生了變化)。

事實上，你會發(fā)現(xiàn)：其實對于每一組數(shù)據(jù)只要判斷最大的那個數(shù)是不是比其余的數(shù)的和都要大，如果成立的話那當(dāng)然就是剩下的所有電池與最大的電池車輪戰(zhàn)，最大值為n-1個數(shù)的和，如果不成立的話那么最大就是n個數(shù)的和的一半，也就是說電池是一定可以全部用完的。講一下簡單的證明過程，每次先對N個數(shù)進(jìn)行排序，然后最大電池每次與其余電池PK一小時，如此進(jìn)行下去最后必然是三種情況中的一種即（2 1 1）（1 1）（1 1 1），這三種情況都是可以用完的，所以電池必定會全部用完。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n,T;
	int buf[1000];
	double ans;
	cin>>T;
	for(int t=1;t<=T;++t)
	{
		ans=0;
		for(int i=0;i<n;i++){
			scanf("%d", &buf[i]);
		    ans+=buf[i];
		}
		sort(buf,buf+n);
		if(buf[n-1]>ans-buf[n-1])
			ans=ans-buf[n-1];
		else
			ans=ans*1.0/2;
       printf("%.1f\n", ans);
	}
	return 0;
}   

CJOJ P1236 - 指數(shù)序列求和###

Description
求 \(1^b+2^b+…+a^b\) 的和除以10000的余數(shù)。

Input
第一行包含一個正整數(shù)N，表示有N組測試數(shù)據(jù)
接下來N行每行包含兩個正整數(shù)a和b

Output
輸出共N行，每行一個對應(yīng)的答案

Sample Input
1
2 3

Sample Output
9

Hint
數(shù)據(jù)范圍：
對于30%數(shù)據(jù) \(n≤10，a，b≤1000\)
對于100%數(shù)據(jù) \(n≤100，a，b≤10^9\)

分析
快速冪+同類余數(shù)優(yōu)化
暴力分30分不用解析了，就算你用了快速冪，for循環(huán)一遍，還是30分。
for循環(huán)的時候循環(huán)枚舉到a是一定不可能的，我們知道在我們?nèi)∧さ臅r候 a*c%b =a%b*c%b，所以我們利用這個原理，因為是挨著快速乘，他們?nèi)∧ひ院蟮臄?shù)也一定是連著的，分析之后就會發(fā)現(xiàn)a^b和(a+mod)b對答案的影響是一樣的，證明是顯然的。
所以說我們對于任意 i^b 都可以寫成 (i%mod)^b ，由于 mod 10000，模數(shù)只有一萬可以推算出mod10000相同的數(shù)，分在一組，比如2333和23333和233333就分在一組。
然后，這一組有多少個數(shù)，我就把這個組的數(shù)快速冪求出b次方然后乘組中元素個數(shù)就行了（詳情看代碼）。

#include<bits/stdc++.h>
using namespace std;
int mod=10000;

int Pow(int x,int y)
{
	int base=x, cnt=1;
	while(y>0)
	{
		if(y%2==1)
			cnt=cnt*base%mod;
		base=base*base%mod;
		y=y>>1;
	}
	return cnt;
}

int main()
{
	int n,a,b,ans;
	cin>>n;
	while(n>0)
	{
		n=n-1, ans=0;
		cin>>a>>b;
		int k=min(mod-1,a);
		for(int i=1;i<=k;++i)
			//1~a范圍內(nèi)余數(shù)同為i的一共有 1+(a-i)/mod 組，統(tǒng)計余數(shù)相同的這組數(shù)的冪次方 
			ans=(ans+(1+(a-i)/mod)*Pow(i,b)%mod)%mod;
			
		cout<<ans<<endl;
	}
	return 0;
}

化學(xué)反應(yīng)###

Description####

有 N 種不同的物質(zhì)，每種物質(zhì)有兩個屬性——“能量”和“活度”。 N 種中的任意兩種物質(zhì)都可以發(fā)生反應(yīng)；反應(yīng)放熱為兩種物質(zhì)的“能量”之差加一再乘上“活度”的較大值。
換句話說，設(shè)第 i 種物質(zhì)的能量和活度分別為 Ai 和 Bi，則 i 和 j 反應(yīng)的放熱為 (| Ai-Aj |+1) * max(Bi, Bj)
現(xiàn)在你需要選出兩種物質(zhì)，最小化它們反應(yīng)放出的熱量。這個最小值是多少？

Input####

本題包含多組測試數(shù)據(jù)，第一行為測試數(shù)據(jù)組數(shù) T。
對于每組數(shù)據(jù)：
第一行一個正整數(shù) N，表示物質(zhì)種類數(shù)。
接下來 N 行每行兩個正整數(shù) Ai、 Bi，表示第 i 種物質(zhì)的“能量”和“活度”。

Output####

輸出一行一個正整數(shù)，最小放熱。 注意這個數(shù)可能需要 64 位整型來存儲。

Sample Input####

1
7
19 5
5 6
1 2
8 4
25 10
12 3
9 6

Sample Output####

12

數(shù)據(jù)范圍：####

對于 40%的數(shù)據(jù)，N<=1000，T<=5
對于另外 20%的數(shù)據(jù)，N<=10^5，Ai、 Bi<=10^3，T=1
對于 100%的數(shù)據(jù)，N<=10^5，Ai、 Bi<=10^9，T<=40

分析：
40%的數(shù)據(jù) $ N<=1000，O(n^2)$ 的復(fù)雜度將任意兩種物質(zhì)進(jìn)行兩兩反應(yīng)，反應(yīng)的最小值即為所求答案。復(fù)雜度 \(O(T*n^2)\)。
對于另外20%的數(shù)據(jù)，\(N<=10^5\)，且 \(Ai Bi<=10^3，T=1\)，可以發(fā)現(xiàn)物品的種類數(shù)很多，但是能量和活度的值域很小。如果我們對每種物質(zhì)按照活度進(jìn)行從小到大排序，本問題的關(guān)鍵在于找到 Bj<=Bi,且 | Aj-Ai |最小（即能量最接近i物質(zhì)）的j物質(zhì)。
由于 $ Bi<=10^3$，因此開vector值域活度的桶，將活度相同的物質(zhì)丟進(jìn)同一類桶中，從小到大排序后對于每一個Bi，查找B1~Bi的桶內(nèi)所有的元素并讓它們相互反應(yīng)，最小的 | Ai-Aj |即為在兩種物質(zhì)活度最大值為Bi時反應(yīng)的最小熱量，
最后取整個反應(yīng)里的最小值即為所求的答案。復(fù)雜度 \(O(T*10^3*n)\)。
對于100%的數(shù)據(jù)，$ Ai Bi<=10^9$ 重新回到本題的關(guān)鍵問題，在于對于活度為Bi的物質(zhì)，要找到 Bj<=Bi,且 | Aj-Ai |最小（即能量最接近i物質(zhì)）的j物質(zhì)。
因此首先還是按照活度從小到大進(jìn)行排序，然后根據(jù)排序后物質(zhì)的活度 Bi 從小到大進(jìn)行枚舉，對于每一個 Bi 查找前面已經(jīng)枚舉完成的 j 物質(zhì)(必定有Bj<=Bi)，找到能量值恰好大于等于Ai的Aj，即為兩種物質(zhì)活度最大值為Bi時反應(yīng)的最小熱量，
接下來考慮如何查找 i 物質(zhì)之前，能量值與 i 最接近的物質(zhì)j，如果暴力去逐個比較，那么最壞的復(fù)雜度依然會達(dá)到 \(O(n^2)\)。最快的查找方法當(dāng)然是二分查找了，要想使用二分查找那么i之前的物質(zhì)能量屬性 Aj 應(yīng)當(dāng)維護(hù)一個有序序列。
怎么維護(hù)物質(zhì)i之前的能量屬性Aj有序呢？
方法①： 插入排序
方法②： Set
最終時間復(fù)雜度 $ O(T*nlogn) $ ，Set常數(shù)巨大，很可能會被卡掉

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm> 
using namespace std; 
#define l_b lower_bound
#define w1 first
#define w2 second
#define m_p make_pair
#define LL long long 
typedef pair<int,int> PII;
const int maxn=100005;
set<int> f;
set<int>::iterator lsh;
int T,N;
int a[maxn],b[maxn];
PII ls[maxn]; 
int main()
{    
	scanf("%d",&T);    
	for (int gb=1;gb<=T;gb++)    
	{        
		scanf("%d",&N);        
		for (int i=1;i<=N;i++) scanf("%d %d",&a[i],&b[i]);        
		for (int i=1;i<=N;i++) ls[i]=m_p(b[i],a[i]);        
		sort(ls+1,ls+N+1);        
		for (int i=1;i<=N;i++) a[i]=ls[i].w2,b[i]=ls[i].w1;        
		LL minc=1000000000;        
		minc=(LL)minc*minc;        
		f.clear();        
		for (int i=1;i<=N;i++)        
		{            
			if (i!=1)            // i不是第一個，去尋找i前面活度Bj<=Bi，且能量最接近ai的物質(zhì)j 
			{                
				lsh=f.l_b(a[i]);  // 尋找i前面能量值第一個大于等于a[i]的位置              
				if (lsh!=f.end())                    
					minc=min(minc,(LL)b[i]*((*lsh)-a[i]+1));                
				if (lsh!=f.begin())    // 尋找i前面能量值恰好小于a[i]的位置               
				{                    
					--lsh;                    
					minc=min(minc,(LL)b[i]*(a[i]-(*lsh)+1));                
				}            
			}            
			f.insert(a[i]);        
		}        
		cout<<minc<<endl;    
	}    
	return 0;
}