A - DDL 的恐懼
現(xiàn)有n個(gè)作業(yè)，每個(gè)作業(yè)都有DDL，沒在DDL之前做完作業(yè)的話，就沒扣掉相應(yīng)的分。
輸入
第一行輸入指的是準(zhǔn)備要輸入程序的有幾組數(shù)據(jù)，接下來每組數(shù)組有兩行，第一行是每個(gè)作業(yè)的DDL，第二行是每個(gè)作業(yè)的分值
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
輸出
0
3
5
思路
考慮貪心算法。
每個(gè)作業(yè)都有分值，所以當(dāng)然要考慮把分值大的先拿下。所以把數(shù)據(jù)給存進(jìn)結(jié)構(gòu)體了以后，就先按找分值降序，日期降序保存，這樣就保證先插分值高的數(shù)據(jù)，分值相同的數(shù)據(jù)就先插日期比較靠后的，這樣就會(huì)對(duì)其他數(shù)據(jù)的插入產(chǎn)生最小的影響。
總結(jié)
對(duì)一道題考慮貪心算法的時(shí)候至少要自己先簡單證明一下正不正確，如果有些摸棱兩可的地方不妨多想想，或許有更好的貪心算法。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
struct day {
int a, b;//a記錄的是ddl，b記錄的是扣分
bool operator<(const day& p) const {
//第一關(guān)鍵字降序，第二關(guān)鍵字降序
if (b != p.b) return b > p.b;
return a > p.a;
}
}days[9999];
bool vis[9999];//用來插這次訪問過的
void cal(int k)//用來計(jì)算要扣掉多少分
{
int sum=0;
int j;
for (int i = 0; i < k; i++)
{
for (j = days[i].a; j >= 1; j--)
{
if (!vis[j])
{
vis[j] = true;
break;
}
}
if (j == 0)
sum += days[i].b;
}
cout << sum<<endl;
for (int i = 0; i < 3000; i++)
vis[i] = false;
}
int main()
{
int n;
cin >> n;//輸入一共有多少組數(shù)據(jù)
for (int i = 0; i < n; i++)
{
int k;
cin >> k;//輸入這組數(shù)據(jù)中一共有多少個(gè)ddl
for (int j = 0; j < k; j++)
{
cin >> days[j].a;
}
for (int j = 0; j < k; j++)
{
cin >> days[j].b;
}
sort(days, days + k);
cal(k);
}
}
B - 四個(gè)數(shù)列
現(xiàn)有4個(gè)數(shù)列，現(xiàn)要從4個(gè)數(shù)列中挑出4個(gè)數(shù)字其和為0，考慮其組合的個(gè)數(shù)。
輸入
一行是一組數(shù)據(jù)
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
輸出
5
思路
一開始我使用的map，之前在leetcode上做過相似的題，只是那道題是用unordered_map做的，這次不支持C++11，就只能用map，復(fù)雜度高了一點(diǎn)，做出來的復(fù)雜度是O(n^2logn)，和上課學(xué)的方法復(fù)雜度一樣，但是可能常數(shù)比較大，所以沒過。
map方法代碼
#include<iostream>
#include<map>
using namespace std;
int A[4000];//四個(gè)數(shù)組
int B[4000];
int E[4000];
int F[4000];
int main()
{
int n;
cin >> n;
int k = 0;
bool pan = true;
map<int, int> C;
for (int i = 0; i < n; i++)
{
scanf("%d %d %d %d",&A[i],&B[i],&E[i],&F[i]);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[A[i] + B[j]]++;
}
}
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j =0; j < n; j++)
{
//if (C.count(-(E[i] + F[j])) != 0)
sum+=C[-(E[i] + F[j])];
}
}
cout << sum;
這樣的話只能乖乖用課上的方法，一看四個(gè)數(shù)組，第一個(gè)想到的可能是一個(gè)四重循環(huán)枚舉所有的數(shù)得到結(jié)果，但是復(fù)雜度是O（）根本不能接受好嗎。
所以可以先每兩個(gè)數(shù)組作為一個(gè)單位，枚舉其中的每兩個(gè)數(shù)的和，這樣的話4個(gè)數(shù)組就變成了兩個(gè)數(shù)組A和B，復(fù)雜度降到了O（）,這可以接受了，在得到B后，要是把B給升序排列，然后從B中找A中對(duì)應(yīng)的數(shù)的時(shí)候，還能二分查找，那么復(fù)雜度還能降低，是O（
）更優(yōu)！
總結(jié)
這道題考慮降低復(fù)雜度以及二分查找的使用，啟示是只要有序的排列都能二分降低復(fù)雜度
AC代碼
#include<stdio.h>
#include<algorithm>
using namespace std;
int A[5000];
int B[5000];
int C[5000];
int D[5000];
int E[9999999];
int F[9999999];
int cal(int n,int k)
{
int sum=0,ans=-1;
n=-n;
int l=0,r=k-1;
int mid=(l+r)>>1;
while(l<=r)
{
mid=(l+r)>>1;
if(F[mid]>=n){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(F[ans]!=n)
return 0;
else
{
for(int i=ans;i<k;i++)
{
if(F[i]==n)
sum++;
else
break;
}
}
return sum;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
int k=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
E[k]=A[i]+B[j];
k++;
}
}
k=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
F[k]=C[i]+D[j];
k++;
}
}
sort(F,F+k);
int sum=0;
int bb;
for(int i=0;i<k;i++)
sum+=cal(E[i],k);
printf("%d",sum);
}
C - TT 的神秘禮物
現(xiàn)在給出一個(gè)數(shù)組，然后讓數(shù)組中每兩個(gè)序號(hào)不同的數(shù)相減取絕對(duì)值生成一個(gè)新數(shù)組，求這個(gè)新數(shù)組的中位數(shù)
輸入
每兩行為一組數(shù)據(jù)，第一行代表這個(gè)數(shù)組有多少個(gè)數(shù)，第二行輸入這個(gè)數(shù)組
4
1 3 2 4
3
1 10 2
輸出
1
8
思路
求中位數(shù)要排序，排序之后就會(huì)有序，有序就能用二分。
如果順著題目中的思路，那就是先給數(shù)組求中位數(shù)然后排序再找中位數(shù)，但是這樣的結(jié)果是復(fù)雜度O（）不能接受。
那就改良，使用二分。
首先要去掉絕對(duì)值，那么就給目標(biāo)數(shù)組排序，這樣從大到小相減的時(shí)候就不用求絕對(duì)值了。然后開始對(duì)所有有可能的答案進(jìn)行二分搜索，已知的答案的最大值是目標(biāo)數(shù)組的最后一個(gè)數(shù)減去第0個(gè)數(shù)，但是最小的未知，但一定大于等于0，那就設(shè)置最小值是0，這樣的話對(duì)這里面的數(shù)進(jìn)行二分，每次二分的結(jié)果都去數(shù)組里面找他所在的名次，如果名次是中位數(shù)的名次了，那么中位數(shù)就在它的附近。
那么名次怎么找呢，那就要枚舉，先有一個(gè)二分出來的數(shù)x，讓數(shù)組里面每個(gè)數(shù)與其后的所有數(shù)相減，這時(shí)候用二分枚舉，得到最后一個(gè)差值<=x的數(shù)的位置，每個(gè)數(shù)組里的數(shù)都這么做一遍，就能得到這個(gè)數(shù)x的名次。
一直按上面的步驟計(jì)算x的名次，直到枚舉x的左右游標(biāo)相等時(shí)，即x是目標(biāo)中位數(shù)。
總結(jié)
這道題考察二分搜索，是二分答案的典型題，使用二分搜索能有效降低代碼的復(fù)雜度。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
int cat[999999];
int n;
int search(int mid)
{
int r, l;
int midd;
int sum = 0;
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
ans = 0;
r = n - 1;
l = i;
while (r >= l)
{
midd = (r + l) >> 1;
if (cat[midd] - cat[i] <= mid)
{
ans = midd;
l = midd + 1;
}
else
r = midd - 1;
}
sum += (ans - i);
}
return sum;
}
int main()
{
while (cin >> n)
{
for (int i = 0; i < n; i++)
scanf_s("%d", &cat[i]);
sort(cat, cat + n);
long long r = cat[n - 1] - cat[0];
long long l = 0;
long long mid;
int result = n * (n - 1) >> 1;
if (result % 2 == 1)//他是奇數(shù)
result = (result >> 1) + 1;
else
result = result >> 1;
long long th;
long long now;
while (r >= l)
{
mid = (r + l) >> 1;
th = search(mid);
if (th >= result)
{
now = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d\n", now);
}
}
