T1

二次函数在定义域范围内求最小值；
利用初中数学公式
-b/2*a即可、

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int N=1e5+7;
int T,n,f;
LL a,b,c;
int main(){
//	freopen("shopping.in","r",stdin);
//	freopen("shopping.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		a=0,b=0,c=0;
		scanf("%d%d",&n,&f);
		for(int i=1;i<=n;i++){
			long long x,y,z;
			scanf("%lld%lld%lld",&x,&y,&z);
			a+=x;
			b+=y;
			c+=z;
		}
		long double kk=1.0*-b/(2*a);
		if(kk>=1.0*f){
			cout<<f<<"\n";
			continue;
		}
		if(kk<=1.0*1){
			cout<<1<<"\n";
			continue;
		}
		LL tt=-b/(2*a);
		if(kk<=1.0*tt+0.5){
			cout<<tt<<"\n";
		}else cout<<tt+1<<"\n";
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
2
7 149
76 -7370 -10000
22 655 -827
68 3578 -9060
52 -2330 8694
6 -9309 6620
1 3423 594
42 -8664 -2332
3 158
94 1780 3736
10 539 6924
71 -1680 3079
*/

T2

显然，编号越大的节点值越大越优
又因为次数无线，所以对于一个联通块内就可以贪心

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int N=2e5+7;
struct edge{
	int v,nxt;
}e[N<<1];
int n,m,L,cur,cnt;
int head[N],vis[N],w[N],c[N];
LL sum[N],ans;
void add_edge(int u,int v){
	e[++cnt]=(edge){v,head[u]};
	head[u]=cnt;
}
void dfs(int u){
	vis[u]=cur;
	c[cur]++;
	sum[cur]=sum[cur]+w[u];
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].v;
		if(!vis[to]){
			dfs(to);
		}
	}
}
int main(){
	freopen("pmlaw.in","r",stdin);
	freopen("pmlaw.out","w",stdout);
	scanf("%d%d%d",&n,&m,&L);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	for(int i=1;i<=n;i++) if(!vis[i]) cur++,dfs(i);
	for(int i=n;i>=1;i--){
		int tt=vis[i];
		c[tt]--;
		if(sum[tt]-c[tt]>=L){
			ans=ans+1LL*i*L;
			sum[tt]-=L;
		}else{
			ans=ans+1LL*i*(sum[tt]-c[tt]);
			sum[tt]=c[tt];
		}
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
3 1 4
2 3 3
1 2
*/

9.26考试总结

原文：https://www.cnblogs.com/Aswert/p/13737653.html