美团算法笔试8.29
第一题：AC100%（丁香花）
import sys
n = int(sys.stdin.readline().strip(' ').strip('\n').strip(' '))
arr = list(map(int,sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' ')))
record = {}
res =0
for i in range(len(arr)):
if arr[i] not in record:
record[arr[i]]=0
record[arr[i]] +=1
for key in record:
if key< arr[i]:
res+= 1
print(res) 第二题：AC100%（放书）
import sys
from bisect import bisect_right,bisect_left
n = int(sys.stdin.readline().strip(' ').strip('\n').strip(' '))
arra = list(map(int,sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' ')))
arrb = list(map(int,sys.stdin.readline().strip(' ').strip('\n').strip(' ').split(' ')))
arra = sorted(arra,reverse=True)
arrb = sorted(arrb)
mode = int(1e9+7)
res = 1
for i in range(n):
flag = arra[i]
idx = bisect_left(arrb,flag)
tres = n-idx -i
if tres<=0:
res = 0
break
res = (res*tres)%mode
print(res)
第三题：AC100%（字符串）
import sys
s = sys.stdin.readline().strip(' ').strip('\n').strip(' ')
a = sys.stdin.readline().strip(' ').strip('\n').strip(' ')
records = []
record = {}
for i in range(len(s)-1,-1,-1):
record[s[i]] = i
records.append(record.copy())
records = records[::-1]
flag = False
for c in a:
if c not in record:
flag= True
break
if flag:
print(-1)
else:
res = 0
n = len(s)
idx = 0
i= 0
while i<len(a):
c = a[i]
if idx>=n :
idx = 0
continue
trecord = records[idx]
if c not in trecord:
res += (n- idx)
idx = 0
continue
next_idx = trecord[c]
res += (next_idx-idx)
idx = next_idx+1
i+=1
print(res) 第四题：AC36%（割草） 这一题我觉得需要用到二维差分数组，但是不管怎么样在n和m都是1e5的时候感觉都不好处理。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
using namespace std;
const int maxn = 1005,maxm = 1005;
int book[maxn][maxm];
int main() {
int n,m,k,res=0;
cin>>n>>m>>k;
int x,y,r;
for (int i = 1; i <n+1 ; ++i) {
for (int j = 1; j <m+1 ; ++j) {
book[i][j] =1;
}
}
// vector<vector<int> >book(n+1, vector<int>(m+1,1));
for (int tt = 0; tt < k; ++tt) {
cin>>x>>y>>r;
for (int i = 1; i <n+1 ; ++i) {
for (int j = 1; j <m+1 ; ++j) {
if ((i-x)*(i-x)+(j-y)*(j-y)<= r*r){
book[i][j] =0;
}
}
}
if (tt!=k-1){
for (int i = 1; i <n+1 ; ++i) {
for (int j = 1; j <m+1 ; ++j) {
book[i][j] +=1;
}
}
}
}
for (int i = 1; i <n+1 ; ++i) {
for (int j = 1; j <m+1 ; ++j) {
res+=book[i][j];
}
}
cout<<res;
return 0;
}
